kmp的最小循环节

KMP最小循环节、循环周期：

• 定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。
• （1）如果len可以被len – next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。
• （2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。
• 理解该定理，首先要理解next数组的含义：next[i]表示前面长度为i的子串中，前缀和后缀相等的最大长度

抽象的解释参考这个：”https://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

k    m   x     j     i

由上，next【i】=j，两段红色的字符串相等（两个字符串完全相等），s[k….j]==s[m….i]

设s[x…j]=s[j….i](xj=ji)

则可得，以下简写字符串表达方式

kj=kx+xj;

mi=mj+ji;

因为xj=ji，所以kx=mj，如下图所示

 k   m     a    x    j     i

设s[a…x]=s[x..j](ax=xj)

又由xj=ji，可知ax=xj=ji

即s[a…i]是由s[a…x]循环3次得来的。

而且看到没，此时又重复上述的模型，s[k…x]=s[m…j]，可以一直递推下去

最后可以就可以递推出文章开头所说的定理了。

最后再举两个相关例子

abdabdab  len:8 next[8]:5

最小循环节长度：3（即abd）   需要补的个数是1  d

ababa  len:5 next[5]：3

最小循环节长度：2（即ab）    需要补的个数是1  b

下面一道经典例题进行解释

Power Strings

Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;;
char str[MAXN];
int _next[MAXN];

void getNext(char *p)
{
    int j,k;
    j=0;
    k=-1;
    int len=strlen(p);
    _next[0]=-1;
    while(j<len)
    {
        if(k==-1||p[j]==p[k])
        {
            j++;
            k++;
            _next[j]=k;
        }
        else k=_next[k];
    }
}
int main()
{
    while(scanf("%s",&str),str[0]!='.')
	{
	    getNext(str);
        int len=strlen(str);//str字符串的个数 
        int t=len-_next[len];//最小循环节 
        if(len%t==0)//原串是否能被循环节整除
		printf("%d\n",len/t);
		else printf("1\n");
    }
    return 0;
}