HDU - 1238 KMP：最大公共子串

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1238
题目大意：找出最长的一个子串，所有串中都出现过它或它的逆序。

这个子串一定在字符串1出现。那么就二分长度枚举字符串1的子串。再用kmp判断是否在其他的字符串存在。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int Next[105][105];
char T[105][105], ct[105];

void getnext(int p, char *ptr)
{
    int i,n,k;
    n=strlen(ptr);
    k=-1;Next[p][0]=-1;i=0;
    while(i<n){
        if(k==-1||ptr[i]==ptr[k]){// k=-1用于指针i的移动 结合k=Next[k]看
            i++;k++;Next[p][i]=k;
        }
        else k=Next[p][k];
    }
}

int kmp(int p, char *a,char *b)//匹配ab两串，a为父串
{
    int i=0,j=0;
    int len1=strlen(a), len2=strlen(b);
    while(i<len1&&j<len2)
    {
      if(j==-1||a[i]==b[j])
        ++i,++j;
      else
        j=Next[p][j];
    }
    if(j==len2)
        return  i-j;
    else
        return -1;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        int n;scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%s", T[i]);
        }
        for(int i=1; i<=n; i++){
            getnext(i, T[i]);
        }
        int L=0, R=strlen(T[1]), kk=0;
        int Len=strlen(T[1]);
        while(L<=R){
            int mid=(L+R)/2, fg=0;
            for(int i=0; i<=Len-mid; i++){

                int cut=0;
                for(int j=i; j<i+mid; j++){
                    ct[cut++]=T[1][j];
                }
                ct[cut]=0;

                int f=1;
                for(int k=2; k<=n; k++){
                    if(kmp(k, T[k], ct)==-1&&kmp(k, T[k], strrev(ct))==-1){
                        f=0;
                    }
                }
                if(f==1){
                    fg=1;
                    break;
                }

            }
            if(fg==1){
               L=mid+1, kk=mid;
            }
            else{
                R=mid-1;
            }
        }
        printf("%d\n", kk);

    }

    return 0;
}
/* 2 3 ABCD BCDFF BRCD 2 rose orchid */