POJ3080 Blue Jeans KMP+枚举

　　每个字符串的长度为60，而且字符串的数量很少，容易想到枚举水过。这题目的数据，就算纯暴力不优化，貌似也能过。加个KMP匹配也看不出多少优势。。。我在写KMP的时候，犯了一个低级的错误，居然把匹配过程写错了，导致wa了很久，下次吸取教训！！！

 1 //STATUS:C++_AC_0MS_164KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 #include<map>
13 using namespace std;
14 #define LL __int64
15 #define pii pair<int,int>
16 #define Max(a,b) ((a)>(b)?(a):(b))
17 #define Min(a,b) ((a)<(b)?(a):(b))
18 #define mem(a,b) memset(a,b,sizeof(a))
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N=70,INF=0x3f3f3f3f,MOD=1999997;
22 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
23 
24 char s[12][N],ans[N];
25 int next[N];
26 int T,n,m,len;
27 
28 void getnext(char *a,int len)
29 {
30     int j=0,k=-1;
31     next[0]=-1;
32     while(j<len){
33         if(k==-1 || a[k]==a[j])
34             next[++j]=++k;
35         else k=next[k];
36     }
37 }
38 
39 int cmp(char *a,int len)
40 {
41     int i,j,ok,k;
42     for(i=1;i<n;i++){
43         for(j=ok=k=0;j<m;j++){
44             while(k>0 && s[i][j]!=a[k])k=next[k];
45             if(s[i][j]==a[k])k++;
46             if(k==len){ok=1;break;}
47         }
48         if(!ok)return 0;
49     }
50     return 1;
51 }
52 
53 int main()
54 {
55  //   freopen("in.txt","r",stdin);
56     int i,j,maxlen,ok,t;
57     scanf("%d",&T);
58     while(T--)
59     {
60         m=60;
61         maxlen=-INF;
62         scanf("%d",&n);
63         for(i=0;i<n;i++)
64             scanf("%s",s[i]);
65         for(i=0;i<m;i++){
66             for(j=i+3;j<=m;j++){
67                 len=j-i;
68                 if(len<maxlen)continue;
69                 getnext(*s+i,len);
70                 if(cmp(*s+i,len)){
71                     t=s[0][j];
72                     s[0][j]='\0';
73                     if(len>maxlen){
74                         maxlen=len;
75                         strcpy(ans,*s+i);
76                     }
77                     else if(strcmp(ans,*s+i)>0)
78                         strcpy(ans,*s+i);
79                     s[0][j]=t;
80                 }
81             }
82         }
83 
84         printf("%s\n",maxlen>2?ans:"no significant commonalities");
85     }
86     return 0;
87 }