1 // File Name: getnext.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月09日 星期二 22时35分02秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25  26 using namespace std; 27 char str1[300]; 28 char str[4004][300]; 29 int next[305]; 30 void split(int x ,int y ) 31 { 32    int t = -1; 33    for(int i = x ;i <= y ;i ++) 34    { 35       str1[++t] =  str[1][i]; 36    } 37    str1[++t] = ‘\0‘; 38 } 39 void getnext() 40 { 41     int len = strlen(str1); 42     next[0] = -1;  43     int k = -1; 44     int j = 0 ;  45     while(j <= len - 1) 46     { 47         if(k == -1 || str1[j] == str1[k]) 48         { 49             ++j;  50             ++k; 51             next[j] = k ; 52         } 53         else { 54             k = next[k]; 55         } 56     } 57 } 58 int  kmp(int k) 59 { 60     int j = 0 ;  61     int i = 0 ; 62     int len = strlen(str1); 63  64     while(j < strlen(str[k])) 65     { 66        if(i == -1 || str1[i] == str[k][j]) 67        { 68          i ++ ;  69          j ++ ;  70        }else{ 71          i = next[i]; 72        } 73        if(i == len) 74        { 75           return 1;  76        } 77     } 78     return 0 ; 79 } 80 int n ; 81 char ans[100]; 82 int maxlen;  83 int  solve(int x, int y) 84 { 85     split(x,y); 86 //    puts(str1); 87     getnext(); 88     for(int i = 2 ;i <= n;i ++) 89     { 90       if(!kmp(i)) 91       { 92          return 0 ;   93       } 94     } 95     //puts(str1); 96     if(y - x + 1 > maxlen) 97     { 98          strcpy(ans,str1); 99          maxlen = y-x +1; 100     }101     else if(y -x +1 == maxlen)102     {103        if(strcmp(ans,str1) > 0)104            strcpy(ans,str1);105     }106     return 1;107 }108 int main(){109     while(scanf("%d",&n),n)110     {111       maxlen = 0 ; 112       int minlen = 1e9;113       for(int i = 1 ;i <= n;i ++)114       {115         scanf("%s",str[i]);116         if(strlen(str[i]) < minlen)117         {118           minlen = strlen(str[i]);119         }120       }121       for(int i = 0 ;i < strlen(str[1]) ;i ++)122         for(int j = i;j < strlen(str[1]) ;j ++)123         {124           if(!solve(i,j) || j-i+1 > minlen)125           {126              break;127           }128         }129      if(maxlen > 0)130       {131         puts(ans);132       }else {133         printf("IDENTITY LOST\n");134       }135     }136     return 0;137 }