kmp的最小循环节

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

kmp的最小循环节

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;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114891.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号