Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:KMP过的代码 关键是要输出的是字典序 比如 PDD 和 ADD 要输出ADD

Posted by 17cndf at 2018-03-05 17:58:01 on Problem 3080
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator