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 |
Re:KMP过的代码 关键是要输出的是字典序 比如 PDD 和 ADD 要输出ADDIn Reply To:KMP过的代码 关键是要输出的是字典序 比如 PDD 和 ADD 要输出ADD Posted by:apple1997 at 2017-03-10 12:28:51 > #include<cstdio> > #include<cstring> > #include<algorithm> > using namespace std; > int n,alen,Next[70],resl,resr; > char a[70]; > char s[15][70]; > void getNext(int l,int r) > { > Next[0]=Next[1]=0; > for(int i=l+1;i<=r;i++) > { > int j=Next[i-l]; > while(j&&a[i]!=a[j+l]) j=Next[j]; > Next[i+1-l]=a[i]==a[j+l]?j+1:0; > } > } > bool KMP(int k,int l,int r) > { > int len=strlen(s[k]); > int j=l; > for(int i=0;i<len;i++) > { > while(s[k][i]!=a[j]&&(j-l)) j=Next[j-l]+l; > if(s[k][i]==a[j]) j++; > if(j==r+1) return true; > } > return false; > } > bool solve(int n) > { > bool ans=false; > for(int i=0;i<alen;i++) > { > for(int j=i+2;j<alen;j++) > { > bool flag=true; > getNext(i,j); > for(int k=0;k<n;k++) if(!KMP(k,i,j)) flag=false; > if(flag) > { > ans=true; > if(j-i>resr-resl) resr=j,resl=i; > else if(j-i==resr-resl) > { > bool Llarge=true; > for(int t=0;t<=resr-resl;t++) > { > if(a[resl+t]<a[i+t]) break; > else if(a[resl+t]>a[i+t]) > { > Llarge=false; > break; > } > } > if(!Llarge) resr=j,resl=i; > } > } > } > } > return ans; > } > int main() > { > int T,n; > scanf("%d",&T); > while(T--) > { > scanf("%d",&n); > scanf("%s",a); > alen=strlen(a); > n--; > resl=resr=0; > for(int i=0;i<n;i++) scanf("%s",s[i]); > if(!solve(n)) puts("no significant commonalities"); > else > { > for(int i=resl;i<=resr;i++) printf("%c",a[i]); > puts(""); > } > } > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator