A1077 Kuchiguse (20 point(s))

找到相同后缀

1. 原文

原题

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

2. 解析

用string 取存在空格的字符串 getline(cin,str);

从后往前遍历两字符串i，j 相同值存入另一个字符串ans+=str1[i];

ans充当下一个待匹配字符串str1=ans，重新匹配str1，str2

最终的str1值即为答案

3. AC代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	cin>>n;
	getchar();
	string str1,ans;
	getline(cin,str1);
	while(--n)
	{
		string str2;
		getline(cin,str2);
		int i=str1.length()-1; int j=str2.length()-1;
		while (i>=0&&j>=0)
		{
			if (str1[i]==str2[j])
			{
				ans+=str1[i];
			}else{
				break;
			}
			i--; j--;
		}
		reverse(ans.begin(),ans.end());
		str1=ans;
		ans.clear();
	}
	if (str1.length()==0)
	{
		cout<<"nai"<<endl;
	}else{
		cout<<str1<<endl;
	}
	return 0;
}