【PAT甲级 - C++题解】1077 Kuchiguse

1077 Kuchiguse

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?

Input Specification:

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.

Output Specification:

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.

Sample Input 1:

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

Sample Output 1:

nyan~
• 1

Sample Input 2:

3
Itai!
Ninjinnwaiyada T_T
T_T

Sample Output 2:

nai

思路

通过 getline 输入每行字符串，因为每行字符串可能会出现空格。

从大到小枚举第一个字符串的后缀，因为要求的是最长公共后缀，故要从最大的后缀开始判断。

与其它字符串同等长度的后缀进行比较，如果第一个字符串的后缀比当前遍历到的字符串长度都要大，或着两者后缀不相等就直接 break 。

如果得到了一个公共后缀就直接输出，因为是从大到小枚举，所以最早匹配的那个后缀就是最长公共后缀。

如果都没有匹配的后缀，就输出 nai 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
string s[N];
int main()
{
    cin >> n;
    getchar();
    for (int i = 0; i < n; i++)    getline(cin, s[i]);
    //从大到小进行枚举，因为要求的是最长的公共后缀
    for (int k = s[0].size(); k; k--)
    {
        string x = s[0].substr(s[0].size() - k);
        bool is_matched = true;
        //与其它的字符串进行比较
        for (int i = 1; i < n; i++)
            if (k > s[i].size() || x != s[i].substr(s[i].size() - k))
            {
                is_matched = false;
                break;
            }
        //如果已经满足就直接输出
        if (is_matched)
        {
            cout << x << endl;
            return 0;
        }
    }
    //如果都不满足要求，则输出nai
    puts("nai");
    return 0;
}