题意:有个一字符串A(本身不是循环串),然后经过很多次自增变成AAAAA,然后呢从自增串里面切出来一部分串B,用这个串B求出来A的长度。 分析:其实就是求最小循环节…….串的长度 – 最大的匹配。代码如下。===========================================================================================================
#include<stdio.h>
#include<string.h>const int MAXN = 1e6+;
const int oo = 1e9+;char s[MAXN];
int next[MAXN];void GetNext(int N)
{
int i=, j=-;
next[] = -; while(i < N)
{
if(j==- || s[i]==s[j])
next[++i] = ++j;
else
j = next[j];
}
}int main()
{ while(scanf("%s", s) != EOF)
{
int N = strlen(s); GetNext(N); printf("%d\n", N-next[N]);
} return ;
}