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
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 65955 | Accepted: 27243 |
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;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/114891.html原文链接：https://javaforall.net
