学步园

水题，枚举第一个字符串的所有子串，然后去和其他的串匹配，其它地方没什么好多说的，有些细节的地方没注意搞得我wa了好几次。郁闷

要注意输出的是字典序小的，这代码写得太丑了

/*<br /> * File: main.cpp<br /> * Author: Mi<br /> *<br /> * Created on 2011年3月27日, 下午7:02<br /> */<br /> #include <cstdlib><br /> #include <stdio.h><br /> #include <string.h><br /> using namespace std;<br /> /*<br /> *<br /> */<br /> char str[11][65];<br /> int P[70];<br /> void next(char *B,int m,int *P)<br /> {<br /> int i,j=0;<br /> P[1]=0;<br /> for(i=2;i<=m;i++)<br /> {<br /> while(j>0&&B[j+1]!=B[i])<br /> j=P[j];<br /> if(B[j+1]==B[i])<br /> j++;<br /> P[i]=j;<br /> }<br /> }<br /> int kmp(char *A,char *B,int n,int m,int *P)<br /> {<br /> int i,j=0;<br /> for(i=1;i<=n;i++)<br /> {<br /> while(j>0&&B[j+1]!=A[i])<br /> j=P[j];<br /> if(B[j+1]==A[i])<br /> j++;<br /> if(j==m)<br /> return i-j;<br /> }<br /> return -1;<br /> }<br /> int main(int argc, char** argv)<br /> {<br /> int t,h,f,l;<br /> char temp[70],ans[70];<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> int n,tl=0;<br /> memset(ans,0xfff,sizeof(ans));<br /> scanf("%d",&n);<br /> for(int i=1;i<=n;i++)<br /> scanf("%s",str[i]+1);<br /> l=strlen(str[1]+1);<br /> for(int i=1;i<=l;i++)<br /> {<br /> for(int j=i+3;j<=l+1;j++)<br /> {<br /> strncpy(temp+1,str[1]+i,j-i+1);<br /> temp[j-i+1]='/0';<br /> h=strlen(temp+1);<br /> next(temp,h,P);<br /> // puts(temp+1);<br /> f=0;<br /> for(int k=2;k<=n;k++)<br /> if(kmp(str[k],temp,l,h,P)!=-1)<br /> f++;<br /> if(f==n-1)<br /> {<br /> if(h>tl)<br /> {<br /> tl=h;<br /> strcpy(ans,temp+1);<br /> }<br /> else if(h==tl)<br /> {<br /> if(strcmp(temp+1,ans)<0)<br /> strcpy(ans,temp+1);<br /> }<br /> }<br /> }<br /> }<br /> if(tl<3)<br /> puts("no significant commonalities");<br /> else<br /> puts(ans);<br /> }<br /> return 0;<br /> }