扩展kmp找前缀长。。。

Theme Section

5
xy
abc
aaa
aaaaba
aaxoaaaaa

0
0
1
1
2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1100000;

char P[maxn];
int next[maxn];

void pre_exkmp(char P[])
{
    int m=strlen(P);
    next[0]=m;
    int j=0,k=1;
    while(j+1<m&&P[j]==P[j+1]) j++;
    next[1]=j;
    for(int i=2;i<m;i++)
    {
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) next[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<m&&P[i+j]==P[j]) j++;
            next[i]=j; k=i;
        }
    }
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%s",P);
    int n=strlen(P);
    pre_exkmp(P);
    int ans=0;
    for(int i=1;i+ans<n;i++)
    {
        int Len=min(next[i],i);
        while(n-Len<i+Len&&Len>ans) Len--;
        if(Len<=ans) continue;
        for(int j=n-Len;j<n-ans;j++)
        {
            if(next[j]>=n-j)
            {
                ans=max(ans,n-j);break;
            }
        }
    }
    printf("%d\n",ans);
}
    return 0;
}

HDOJ 4763 Theme Section,布布扣,bubuko.com

HDOJ 4763 Theme Section

原文：http://blog.csdn.net/u012797220/article/details/22700545