题意：有2到10个case,每个case里有n个长度都为60的串，求出它们的最长公共子串，如果这个子串的长度 < 3则输出“no significant commonalities”，如果存在多个最长公共子串，则输出字典序最小的那一个。

思路，KMP+枚举，从第0个串中，从长度为60开始，不断选取子串，与其他串做比较，假如在某长度发现了都匹配，压入结果，将同长度的子串按字典序排序，输出最小

1. #include<iostream> 
2. #include<string> 
3. #include<vector>  
4. #define MAXSIZE 60 //输入比较的字符串长度  
5. using namespace std; 
6.  
7. void get_nextval(string T,int *nextval) 
8. { 
9.    int i,j; 
10.    i = 1; 
11.    j = 0; 
12.    nextval[1] = 0;  //经常忘掉这一句  
13.    while(i<T.size()-1) 
14.    { 
15.       if(j==0||T[i]==T[j]) 
16.       { 
17.          ++i; 
18.          ++j; 
19.          if(T[i]!=T[j]) 
20.          { 
21.             nextval[i] = j; 
22.          } 
23.          else 
24.          { 
25.             nextval[i] = nextval[j]; 
26.          } 
27.       } 
28.       else 
29.       { 
30.          j = nextval[j]; 
31.       } 
32.    } 
33. }  
34.  
35. int Index_KMP(string S,string T,int pos) 
36. { 
37.    int i = pos; 
38.    int j = 1; 
39.    int nextval[255]; 
40.    get_nextval(T,nextval); 
41.    while(i<=S.size()-1&&j<=T.size()-1) 
42.    { 
43.       if(j==0||S[i] == T[j]) 
44.       { 
45.          i++; 
46.          j++; 
47.       } 
48.       else 
49.       { 
50.          j = nextval[j]; 
51.       } 
52.    } 
53.    if(j>T.size()-1) 
54.       return i - T.size()+1; 
55.    else 
56.       return 0; 
57. } 
58.  
59. int main() 
60. { 
61.    int cas,n; 
62.    string head = "#";  
63.    cin>>cas; 
64.    vector<string> dna; 
65.    vector<string> result; 
66.    for(int i=0;i<cas;i++) 
67.    { 
68.       vector<string> dna; 
69.       cin>>n; 
70.       for(int j=0;j<n;j++) 
71.       { 
72.          string tmp; 
73.          cin>>tmp; 
74.          dna.push_back(head+tmp); 
75.       } 
76.       vector<string> result; 
77.       for(int j=MAXSIZE;j>=3;j--)   //j表示要从第一个串里取出子串的长度  
78.       { 
79.           
80.          for(int s = 1;s<MAXSIZE+2-j;s++) //s表示从第一个串里的第几个字符开始取这个子串  
81.          { 
82.             int flag2 = 1; 
83.             string current = dna[0].substr(s,j); 
84.             for(int l=1;l<dna.size();l++)   //对剩下的各个字符串进行子串匹配  
85.             { 
86.               flag2 = Index_KMP(dna[l],head+current,1); //注意，第一个参数是主串，第二个参数是子串  
87.                
88.                if(flag2==0)                          //假如碰到一个，不是其子串，直接break掉  
89.                   break; 
90.             } 
91.             if(flag2>0)                              //把所有其他字符串都比较过后，发现都是子串，把此结果压到 结果向量中  
92.                result.push_back(current); 
93.         } 
94.         if(result.size()>0)    //把同一个长度比完之后，假如已经有答案了，没必要去比较更小的子串，中断  
95.            break; 
96.      } 
97.      if(result.size()==0) 
98.         cout<<"no significant commonalities"<<endl; 
99.      else 
100.      { 
101.         string small = result[0]; 
102.         for(int j=1;j<result.size();j++) 
103.         { 
104.            if(result[j]<small) 
105.               small = result[j]; 
106.         } 
107.         cout<<small<<endl; 
108.      } 
109.    } 
110.    system("pause"); 
111.     
112. }