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

题目大意

题目给出一系列字符串，找出其中的共同后缀；

解题思路

1. 读入前两个句子，找到其共同后缀；
2. 对接下来的每一个句子都将其与共同后缀比较、并更新共同后缀；
3. 根据共同后缀的情况输出结果并返回零值。

代码

#include<string.h>
#include<stdio.h>
#define maxn 260

int main(){
    char Sen[110][maxn+1];
    int len[110];
    char same[maxn];
    int length=0;
    int N,i,j;
    scanf("%d",&N);
    getchar();
    fgets(Sen[0],maxn,stdin);
    len[0]=strlen(Sen[0])-2;
    fgets(Sen[1],maxn,stdin);
    len[1]=strlen(Sen[1])-2;
    while((len[1]-length>=0)&&(len[0]-length>=0)&&(Sen[0][len[0]-length]==Sen[1][len[1]-length])){
        same[length]=Sen[0][len[0]-length];
        length++;
    }
    for(i=2;i<N;i++){
        fgets(Sen[i],maxn,stdin);
        len[i]=strlen(Sen[i])-2;
        for(j=0;j<length;j++){
            if(same[j]!=Sen[i][len[i]-j]){
                break;
            }
        }
        length=j;
    }
    if(length<=0){
        printf("nai\n");
    }else{
        do{
            length--;
            printf("%c",same[length]);
        }while(length>0);
        printf("\n");
    }
    return 0;
}

运行结果