#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("");
        }
    }
}

• Re:KMP过的代码 关键是要输出的是字典序 比如 PDD 和 ADD 要输出ADD (2101) 17cndf 2018-03-05 17:58:01