浙江财经大学
信息管理与工程学院

PAT(A) 1077. Kuchiguse (20)

本文由 Ocrosoft 于 2016-12-27 14:08:03 发表

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~
    

    Sample Input 2:

    3
    Itai!
    Ninjinnwaiyada T_T
    T_T
    

    Sample Output 2:

    nai
    
    求给出的n个字符串的最长公共结尾。细节处理真是…
    还有类似这种:
    3
    sssss
    ssss
    sss
    的样例

    #include <set>
    #include <map>
    #include <list>
    #include <cmath>
    #include <stack>
    #include <queue>
    #include <ctime>
    #include <string>
    #include <cstdio>
    #include <vector>
    #include <cctype>
    #include <climits>
    #include <sstream>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    #define strend string::npos
    #define ms(a) memset(a,0,sizeof(a))
    #define  rep(a,v,b) for(int a=v;a<b;a++)
    #define  repe(a,v,b) for(int a=v;a<=b;a++)
    typedef long long LL;
    const LL LINF = LLONG_MAX / 2;
    const int INF = INT_MAX / 2;
    const int MAXN = 300000 + 10;
    const int MOD = 1000000009;
    int gcd(int a, int b)
    {
    	if (!b)return a;
    	return gcd(b, a%b);
    }
    /*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
    /*(◕‿‿◕) 签订契约,成为马猴烧酒吧! (◕‿‿◕)*/
    /*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
    using namespace std;
    int main()
    {
    	int n; cin >> n; getchar();
    	string s, ss; getline(cin, s); getline(cin, ss); n -= 2;
    	string::iterator it1 = s.end() - 1, it2 = ss.end() - 1;
    	int ans = min(s.length(), ss.length());
    	while (1)
    	{
    		if (*it1 != *it2 || s.end() - it1 > ans || it1 == s.begin() || it2 == ss.begin())
    		{
    			if (ans > s.end() - it1 - ((*it1 != *it2) ? 1 : 0))
    				ans = s.end() - it1 - ((*it1 != *it2) ? 1 : 0);
    			s = ss;
    			n--;
    			if (n < 0)break;
    			getline(cin, ss);
    			it1 = s.end() - 1, it2 = ss.end() - 1;
    		}
    		else it1--, it2--;
    	}
    	if (!ans)printf("nai\n");
    	else
    	{
    		for (it1 = s.end() - ans; it1 != s.end(); it1++)printf("%c", *it1);
    		printf("\n");
    	}
    	return 0;
    }

    欢迎转载,请保留出处与链接。Ocrosoft » PAT(A) 1077. Kuchiguse (20)

    点赞 (0)or拍砖 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址