POJ 1226 Substrings 폭력 매 거 진 + KMP 알고리즘

/ * 제목 은 몇 개의 문자열 을 드 리 는 것 입 니 다. 이 문자열 들 중 가장 큰 알파벳 개 수 를 찾 으 면 정 역 순 서 를 찾 을 수 있 습 니 다.
모든 문자열 에 공 통 된 부분 이 어야 하기 때문에 그의 하위 문자열 을 마음대로 들 수 있다 는 생각 이다.
나 는 a [1] 를 가 져 온 후에 그의 길이 가 다른 하위 꼬치 를 매 거 했다.
큰 것 부터 작은 것 까지 KMP (하위 문자열, 원 문자열 (2 - n) | (KMP (역순 하위 문자열, 원 문자열 (2 - n)) 이 성립 되면 이 하위 문자열 은 최대 같은 하위 문자열 입 니 다. 큰 것 부터 작은 것 까지 이 문자열 의 길 이 를 직접 출력 하기 때문에 끝 납 니 다. * /

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
using namespace std;
char a[Max][Max];
int next[Max],n;

void findnext(char a[])
{
    int k=-1;
    int j=0;
    next[0]=-1;
    int l=strlen(a);
    while(j<l)
    {
        if(k==-1||a[k]==a[j])
        {
            k++,j++;
            next[j]=k;
        }
        else k=next[k];//                    
    }
}


int KMP(char a[],char b[])
{
    findnext(a);
    int posa=0,posb=0;
    int la=strlen(a),lb=strlen(b);
    while(posa<la&&posb<lb)
    {
        if(posa==-1||a[posa]==b[posb])
        {
            posa++,posb++;//      ，            
        }
        else posa=next[posa];
    }
    if(posa<la)return 0;//    
    //        posa       a          +1 ，   la 
    else return 1;//    ，         return posb-posa;
}


int main()
{
    int i,j,k,l,m,T;
    char reva[Max],revb[Max];
    cin>>T;
    while(T--)
    {
        int min_i=-1;
        int min_l=1000;
        cin>>n;
        for(i=1; i<=n; i++)
        {
            scanf("%s",a[i]);//                          ，      。        ，           
				
        }
        l=strlen(a[1]);
        bool flag=0;//         
        for(i=l;i>0;i--)//         
        {
            for(j=0;j<l-i+1;j++)//     
            {
                int count=0;
                for(k=j;k<=j+i-1;k++)//        
                reva[count++]=a[1][k];
                reva[count]='\0';
                count=0;
                for(k=j+i-1;k>=j;k--)//        
                revb[count++]=a[1][k];
                revb[count]='\0';
                count=0;
                for(k=2;k<=n;k++)//           
                {
                    if(KMP(reva,a[k])||KMP(revb,a[k]))
                    count++;
                }
                if(count==n-1)//count=n-1     ，           
                {
                    flag=1;
                    cout<<strlen(reva)<<endl;
                    break;
                }
            }
            if(flag)
            break;
        }
        if(!flag)
        cout<<0<<endl;

    }
    return 0;
}

KMP 의 응용 및 하위 문자열 의 구 조 를 고찰 합 니 다.매 거 가 뜻밖에도 시간 을 초과 하지 않 았 다.