HDU 3746 (KMP求最小循环节) Cyclic Nacklace
题意：
给出一个字符串，要求在后面添加最少的字符是的新串是循环的，且至少有两个循环节。输出最少需要添加字符的个数。
分析：
假设所给字符串为p[0...l-1]，其长度为l
有这样一个结论：
这个串的最小循环节为 l - next[l]
感觉自己想得不是特别透彻，所以把别人的博客贴上来吧。
里面有个小错误就是：next[i]的值应该为j-k
对于这种情况还可以这样想：
|←②→|←④→|
------------------------
------------------------
|←①→|←③→|
这是同一个字符串
其中红色代表相同的前缀和后缀
前面那段黄的(①段)等于上面对应等长的红的部分(②段)，因为前缀和后缀相同，所以②段和③段相同，③段又和正上方的④段相同，以此类推。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
char p[maxn];
int next[maxn];
void get_next(char* p, int l)
{
int k = -1, j = 0;
next[0] = -1;
while(j < l)
{
if(k == -1 || p[k] == p[j])
{
k++;
j++;
next[j] = k;
}
else k = next[k];
}
}
int main(void)
{
//freopen("3746in.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--)
{
memset(next, 0, sizeof(next));
scanf("%s", p);
int l = strlen(p);
get_next(p, l);
if(next[l] == 0)
{
printf("%d
", l);
continue;
}
int cir = l - next[l];
if(l % cir == 0)
{
puts("0");
continue;
}
printf("%d
", cir - (l % cir));
}
return 0;
}