KMP求字符串最小循环节

时间:2024-10-12 23:34:13

证明1:

对于一个字符串S,长度为L,如果由长度为len的字符串s(字符串s的最小循环节是其本身)循环k次构成,那么字符串s就是字符串S的最小循环节

那么字符串有个很重要的性质和KMP挂钩,即  i - next[i] 为字符串s的长度 i%(i - next[i]) ==0

证明:字符串S由s循环k次构成,那么有S[0-->L-len-1] == S[len-->L-1],即前k-1个循环节和后k-1个循环节构成的字符串相等

那么此时KMP数组的next[L] = k-1个循环节的长度, 也即 next[L] = L-len-1+1 = L - len,那么此时 L - next[L] = len , 所以 L % len = 0,   L % len = k

所以如果字符串存在循环节,那么i % (i - next[i]) ==0,循环节的长度为  i - next[i]

否则,循环节的为字符串本身。

证明2:

t = n-next[n] 为循环节的长度
1、如果next[n]==0,则表示字符串S前后无任何相同的部分,所以字符串S自身为一个循环节,成立
2、如果next[n]!=0  且 字符串S的循环节个数为2
 ①:如果字符串S是完美(即每个循环节都是完整的)
  那么next[n] = n/2    所以 t = n - next[n] = n/2,成立
 ②:字符串S的循环节个数为2,但是位于左边的循环节是完整的,右边的是残缺的
  那么next[n] = 残缺的循环节和完整的循环节的相似长度,所以t = n - next[n]成立
3、如果next[n]!=0 且字符串S的循环节个数k>=3 ,
 那么字符串S从第二个循环节开始到最后一个字符(设长度为len)和字符串S从第一个字符串开始的len个字符相等
 所以t = n - next[n]成立

hdu1358

求每一个前缀是不是循环串,如果是,输出串长和循环的次数。

 #include <stdio.h>
#include <string.h>
const int N = + ;
char str[N];
int next[N];
void makeNext(char *str)
{
int i=,j=-;
next[] = -;
while(str[i])
{
if(j==-||str[i]==str[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
int main()
{ int n;
int tCase = ;
while(true)
{
scanf("%d",&n);
if(n==)
break;
scanf("%s",str);
makeNext(str);
printf("Test case #%d\n",tCase++);
for(int i=; i<=n; ++i)
{
if(i%(i-next[i])== && next[i]!=)//next[i]!=0,如果为0,循环节是本身
printf("%d %d\n",i,i/(i-next[i])); }
puts(""); }
return ;
}

hdu3746

补多少个字符能形成循环串

 #include <stdio.h>
#include <string.h>
const int N = + ; char str[N];
int next[N]; void makeNext()
{
int i = ,j = -;
next[i] = j;
while(str[i])
{
if(j==- || str[i]==str[j])
next[++i] = ++j;
else
j = next[j];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",str);
int n = strlen(str);
makeNext();
int t = n - next[n];
if(t!=n && n%t==)
puts("");
else
printf("%d\n",t-(n-n/t*t));
}
return ;
}