设串为str, 串长为len。
对整个串求一遍next函数，从串结尾开始顺着next函数往前找<=len/3的最长串，假设串长为ans，由于next的性质，所以找到的串肯定满足E……E这种形式，然后就是在str[ans]-str[len-2*ans]中查找是不是包含E，找到就输出，找不到就沿着next向下寻找，缩短串长。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std; const int MAXN = ; char str[MAXN];
char tmp[MAXN];
int nextval[MAXN];
int len; void GetNextVal( char *s, int lenth )
{
int i = , j = -;
nextval[] = -;
while ( i < lenth )
{
if ( j == - || s[i] == s[j] )
{
++i, ++j;
if ( s[i] != s[j] ) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
return;
} bool KMP( char *t, char *s, int lenth, int lenn )
{
//GetNextVal( t, lenth );
int i = , j = ;
while ( j < lenn )
{
if ( i == - || s[j] == t[i] )
{
++i, ++j;
if ( i == lenth ) return true;
}
else i = nextval[i];
//if ( i == lenth ) return true;
}
return false;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%s", str );
len = strlen(str);
GetNextVal( str, len );
int ans = nextval[len];
while ( ans > len/ ) ans = nextval[ans];
while ( ans > )
{
if ( KMP( str, &str[ans], ans, len - ans - ans ) )
break;
ans = nextval[ans];
}
if ( ans < ) printf("%d\n", len/);
else printf( "%d\n", ans );
}
return ;
}