给定一个字符串，求出一个前缀A，使得字符串的构成可以表示成ABABA的形式（B可以为空串）。
输出这个前缀的最大长度。
KMP算法Next数组的使用。
枚举中间的每个位置，可以根据Next数组求出这个位置对应的前缀。然后暴力判断前缀与后缀是否相等即可。
如图，枚举的位置为 i，则Next[i] = j，。然后判断0~j 是否和 k~len是否是相同的。
注意要判断合法性，即前缀 + 中缀的长度不能比当前枚举的位置大，且后缀开始的位置一定要比当前枚举的位置大。
判定完Next[i]后，一定要判定Next[ Next[i] ]，这样递归下去，看看大的如果不符合，小的是否符合。
然而复杂度，我不会证明。
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010 int Next[maxn]; void GetNext(char s[], int len)
{
Next[] = -;
int j = -;
for (int i = ; i < len; i++)
{
while(j > - && s[j+] != s[i])
j = Next[j];
if (s[j+] == s[i]) j++;
Next[i] = j;
}
} int main()
{
int n;
scanf("%d", &n);
for (int ca = ; ca <= n; ca++)
{
char s[maxn];
scanf("%s", s);
int len = strlen(s), ans = ;
GetNext(s, len);//求出Next数组 for (int i = len-; i >= ; i--)
{
int j = i;
while(j > -)
{
if ((j+)* <= i+ && len - (j+) > i)//判断相互的位置的合法性
{
int flag = ;
for (int k = ; k < j+; k++)
if (s[len - (j+) + k] != s[k])
{
flag = ;
break;
}
if (flag) //前缀和后缀匹配
ans = max(ans, j+);
}
j = Next[j]; //判断比它小的是否符合
}
}
printf("%d\n", ans);
} }