hdu 4763 Theme Section（next数组找串中三段相等）

题意：在一个串中找 EAEBE 的形式的最长的E，其中E为一个字符串，也就是说找到前缀与后缀相同，并且串中还存在相同的一段，它们不能重复。

思路：利用next数组，next[len]代表的即是最大的相同的前缀与后缀，然后让 i 从len-1往前遍历找到 i>=2（前面部分最少要有2个字符），在过程中更新最长的长度ans即可。

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define MaxSize 1000005

int _next[MaxSize];

char str[MaxSize];

void GetNext(char t[]){//求next数组

    int j,k,len;

    j=;

    k=-;

    _next[]=-;

    len=strlen(t);

    while(j<len){

        if(k==-||t[j]==t[k]){

            ++j;

            ++k;

            _next[j]=k;//此句可由优化替代

            /*优化（仅保证求KMPIndex时可用。谨慎使用。）

            if(t[j]!=t[k])next[j]=k;

            else next[j]=next[k];

            */

        }

        else k=_next[k];

    }

}

int main(){

    int t,i,k,len,m,ans;

    scanf("%d",&t);

    while(t--){

        scanf("%s",str);

        GetNext(str);//求子串的next数组

        len=strlen(str);

        m=_next[len];//m代表最大的首尾相同长度

        ans=;

        for(i=len-;i>=;--i){

            k=_next[i];//k为i之前与开头重复的长度

            while(k>){

                if(k<=m&&k+k<=i&&i+k<=len){//长度小于m，且三段不重合

                    ans=max(ans,k);

                    break;//当前是最大的长度

                }

                k=_next[k];//next[k]一定小于k

            }

        }

        printf("%d\n",ans);

    }

    return ;

}