HDU4763 Theme Section KMP

程序员文章站 2022-05-02 17:43:07

...

字符串满足EAEBE，E为相同的前后缀，只需在中间找出另一个E即可

利用nxt数组的性质，找出E即可

/*KMP字符串匹配 next[i]记录1~i中相同前后缀长度-1 即相同字符下标位置
171MS	6108K
*/
#include <stdio.h>
#include <string.h>
const int MAX=1e6+5;
char str[MAX];
int next[MAX];
void buildnext(char *str2,int m)//建立next数组
{
    next[0]=-1;
    for (int k=1,i=-1;k<m;k++)
    {
        while (str2[i+1]!=str2[k]&&i!=-1) i=next[i];
        if (str2[i+1]==str2[k]) i++;
        next[k]=i;
    }
}
int main ()
{

    int T;
    scanf ("%d",&T);
    getchar();
    while (T--)
    {
        memset(next,0,sizeof(next));
        int k=-1,i,ans=0;
        char a;
        while (a=getchar())
        {
            if (a=='\n') break;
            str[++k]=a;
        }
        buildnext(str,k+1);
        for (i=next[k];i>=0&&ans==0;i--)
        {
            for (int j=i;j<=k-i&&ans==0;j++)
                if (next[j]==i)
                    ans=i+1;
        }
        printf ("%d\n",ans);
    }
    return 0;
}