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
#include <cstdio> #include <cstring> /*求最长公共后缀 (1)取n个字符串中的最短长度minlen (2)将接收到的n个字符串逆序,转化为求公共前缀 (3)求公共前缀,只需对比字符串前minlen长度的字符(即下标范围:0 -> minlen-1) */ int main() { int n; char str[105][260]; //至多100个字符串,每个字符串至多256个字符 scanf("%d", &n); getchar(); //划重点(1):接受掉换行,不然会被下面的gets()收走 //(1)反转字符串s[i], 转化为求公共前缀 int minlen=256; //划重点(2):n个字符串中取最短长度,初始化为最大 for(int i=0; i<n; i++){ //注:用scanf输入会错,因为无法判断字符串有效长度 gets(str[i]); //gets()会吃掉空格,换行符,故前面须用getchar()/getc()接收 int len=strlen(str[i]); if(len<minlen) minlen=len; //取最小长度 for(int j=0; j<len/2; j++){ //反转字符串str[i], 转化为求公共前缀 char temp=str[i][j]; str[i][j]=str[i][len-1-j]; str[i][len-1-j]=temp; } } //(2)判断所有字符串的第i个字符是否相等 int ans=0; //记录公共前缀有多少个字符相等 for(int i=0; i<minlen; i++){ char c=str[0][i]; //取第一个字符串的第i个字符 bool same=true; for(int j=1; j<n; j++){ //判断其余字符串的第i个字符是否等于c if(str[j][i]!=c){ //只要有一个不等于c,说明公共前缀到此为止 same=false; break; } } if(same) ans++; //若所有字符串的第i位相等时,公共前缀长度ans+1 else break; } //(3)倒序输出公共前缀 => 公共后缀 if(ans){ for(int i=ans-1; i>=0; i--) printf("%c", str[0][i]); } else printf("nai"); //不存在公共前缀 return 0; }