Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个代码#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; vector<string>ans; char b[65]; int pai[65]; char s[12][65]; int lena,lenb; void compute(char b[]) { int k=0; pai[1]=0; for(int q=2;q<=lenb;q++) { while(k>0&&b[k+1]!=b[q])k=pai[k]; if(b[k+1]==b[q])k+=1; pai[q]=k; } } int kmp(char a[],char b[]) { compute(b); int i,q=0; for(i=1;i<=lena;i++) { while(q>0&&b[q+1]!=a[i])q=pai[q]; if(b[q+1]==a[i])q+=1; if(q==lenb)return 1; } return 0; } bool cmp(const string &a,const string &b) { return a.size()>b.size(); } int main() { int i,j,k,T,t; scanf("%d",&T); while(T--) { ans.clear(); bool leap=true; scanf("%d",&t); for(i=0;i<t;i++) { s[i][0]='0'; scanf("%s",s[i]+1); if(strlen(s[i])<=3) { leap=false; break; } } if(!leap)continue; int length=strlen(s[0])-1; for(i=1;i<=length-2;i++) { for(j=i+2;j<=length;j++) { memset(b,0,sizeof(b));b[0]='A'; for(k=i;k<=j;k++)b[k-i+1]=s[0][k]; lenb=j-i+1; for(k=1;k<t;k++) { lena=strlen(s[k])-1; if(!kmp(s[k],b))break; } if(k==t)ans.push_back(string(b+1)); } } if(ans.size()==0)printf("no significant commonalities\n"); else { sort(ans.begin(),ans.end()); stable_sort(ans.begin(),ans.end(),cmp); cout<<ans[0]<<endl; } } //system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator