| ||||||||||
| 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