小工具知识网

当前位置: 首页 > 行业知识 > 蓝桥杯每日一题(kmp)

行业知识

蓝桥杯每日一题(kmp)

2026-11-18 01:46:43 来源:互联网转载

//141 周期

index.php/tags-41973.html" >���一个字符串的所有前缀的循环节出现的最大次数。也就是最小循环节

kmp算法求循环节;

将原串移动,移动后我们得知,四个黑色大括号完全相同。在下图所示的事例中,原串只有两个循环节,加一个红括号。k3加一个红括号的长度就是kmp中的next数组。

字符串长度-next即为循环节长度。

下面的串向右移动的长度为n-next,而next是最大的前后缀相等的长度。所以移动的长度K是最小的循环节。

上面我们做了什么事:我们根据字符串的next数组的最大值,将其向后移动,使得前后缀重合。

又根据一些特点,(移动前后对应位置相等,前后缀对应相等)得到规律。

但是上面作图的前提是一个串去除了后缀之后的剩余长度。比后缀小。否则构成不了关系。

下面这种情况就不能构成后缀是由某个循环体构成的。

#includeusing namespace std;const int N=1e6+10;int n,m;char s[N];int ne[N];//141周期int main(){    int T=0;    while(scanf("%d",&n),n)    {       scanf("%s",s+1);       for(int i=2,j=0;i

上一篇:我想知道他们是怎么弄到vps主

下一篇:揭秘VMD,虚拟镜像设计的奥秘探索