（KMP灵活运用利用Next数组）ThemeSectionhdu4763

#include
#include
#include<string.h>
#include
using namespace std;
#define INF 0x3f3f3f3f
#define N 1000007
char s[N];
int Next[N];
void FindNext()
{
int i=0, j=-1;
int len = strlen(s);
Next[0] = -1;
while(i<len)
{
if(j==-1 || s[i]==s[j])
Next[++i] = ++j;
else
j = Next[j];
}
}
bool KMP(int Start, int End)
{
int i=0, j=Start;
/// i 是子串的开始， j 是母串的开始
/// 0~Start-1 是子串， Start~End-1 是母串，在母串中查找是否含有子串 while(iEnd)
{
while(i==-1 && (s[i]==s[j] && i<Start))
i++, j++;
if(j==Start)
return true;
i = Next[i];
}
return false;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%s", s);
FindNext();
int len = strlen(s);
int j = len;
while(Next[j]>0)
{
/// next[j] 是最大前缀，就是母串的开始位置
/// 因为前缀也是后缀， 所以用总长度减后缀就是母串结束的位置
if(KMP(Next[j], len-Next[j])==true)
break;
j = Next[j];
}
printf("%d\n", Next[j]);
}
return 0;
}