【PAT甲级】1077 Kuchiguse

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1077 Kuchiguse (pintia.cn)
🔑中文翻译：Kuchiguse
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

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~
1
2
3
4

Sample Output 1:

nyan~
1

Sample Input 2:

3
Itai!
Ninjinnwaiyada T_T
T_T
1
2
3
4

Sample Output 2:

nai
1

思路

1. 通过 getline 输入每行字符串，因为每行字符串可能会出现空格。
2. 从大到小枚举第一个字符串的后缀，因为要求的是最长公共后缀，故要从最大的后缀开始判断。
3. 与其它字符串同等长度的后缀进行比较，如果第一个字符串的后缀比当前遍历到的字符串长度都要大，或着两者后缀不相等就直接 break 。
4. 如果得到了一个公共后缀就直接输出，因为是从大到小枚举，所以最早匹配的那个后缀就是最长公共后缀。
5. 如果都没有匹配的后缀，就输出 nai 。

代码

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40