[PAT A1077]Kuchiguse_综合

[PAT A1077]Kuchiguse

题目描述

1077 Kuchiguse （20 分）The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a cat-like personality:

Itai nyan~ (It hurts, nyan~)

Ninjin wa iyada nyan~ (I hate carrots, nyan~)

Now given a few lines spoken by the same character, can you find her Kuchiguse?

输入格式

Each input file contains one test case. For each case, the first line is an integer N (2≤N≤100). Following are N file lines of 0~256 (inclusive) characters in length, each representing a character’s spoken line. The spoken lines are case sensitive.

输出格式

For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write nai.

输入样例1

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

输出样例1

nyan~

输入样例2

3
Itai!
Ninjinnwaiyada T_T
T_T

输出样例2

nai

解析

这个题目真的是令我头大（好吧说实话是关于字符串的处理，自己的技术还不到家），题目的大概意思就是，首先输入一个N，表示输入的字符串的个数，然后输入N个字符串，我们需要输出的是这些字符串最长的公共后缀，如果他们没有公共后缀，我们就输出nai
我的思路是，由于是比较后缀，我就使用reverse函数将所有的字符串转置，这样我们就只需要比较前x个字母就行了，那样出错的几率就会小很多：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(string a,string b)  //这里写比较函数，这样我们就可以使用sort函数将字符串从小到大排列
{
    return a.length() < b.length();
}
int main()
{
    int N;vector<string> sentence(110); //存放字符串scanf("%d\n", &N); //注意！！这里%d后面跟了一个\n，目的就是要消去结尾的换行符，否则用getline会出错for (int i = 0; i < N; i++) getline(cin, sentence[i]);for (int i = 0; i < N; i++) reverse(sentence[i].begin(), sentence[i].end());  //倒转字符串sort(sentence.begin(), sentence.begin() + N, cmp); //按长度升序排序for (int i = 1; i <= sentence[0].length(); i++) {
    bool judge = true;   //判断该趟比较有没有成功string str = sentence[0].substr(0, i);for (int j = 1; j < N; j++) {
    if (str != sentence[j].substr(0, i)) {
    judge = false;break;}}if (!judge) {
    if (str.length() == 1) cout << "nai";else for (int i = str.length() - 2; i >= 0; i--) cout << str[i];break;}if (i == sentence[0].length())for (int i = str.length() - 1; i >= 0; i--) cout << str[i];}return 0;
}

这里我们提一下柳神的思路，具体代码我就不贴了，有心的读者可以自行设计程序解决该问题，解决方法就是首先令str等于第一个字符串，每输入一个字符串就将str与该字符串进行一次比较，取他们的公共后缀为新的str，这样str应该是不断减小减小，最终得到的结果就是我们想要求的后缀。这种方法非常简单，节省空间，非常值得大家学习，大家有时间一定要按照思路把这个代码自己打出来。

[PAT A1077]Kuchiguse