博客

知识支持：

[1]:

KMP学习资料：左神进阶班第一节

[ 提取码：3knt ]

本节内容主要谈谈我对KMP求字符串循环节的理解：

利用KMP算法中的

next

数组可以求出字符串的循环次数，间接就可以求出循环节的内容和循环节长度。

结论：


长度为 len 的字符串, 如果




(len - next[len]) | len


，则循环次数为


len / (len - next[len])，


否则为1。

（字符串下标从 0 开始）

分三种情况讨论

情况①：显然  len-next[len] | len , 循环次数为 2

情况②：len-next[len] 一定不整除 len，证明如下：

假设 s串 由若干个 a 串和 b 串组成，为方便表述，就固定有4个a串和1个b串，且假设|a| = a , |b| = b：

假设 len-next[len] | len , 即 2a+b | 4a+b;

由带余除法可得 b = ka+r; ( 0 <= r < a)

那么 2a+b | 4a+b ⇔ (2+k)a+r | (4+k)a+r;

相当于 [(4+k)a+r] % [(2+k)a+r] = 0;

下面我们来化简这个式子：

[(4+k)a+r] % [(2+k)a+r] = [(2+k)a+r+2a] % [(2+k)a+r] = 2a%[(2+k)a+r];

易得 (2+k)a+r > 2a;(k和r不会同时为0,除非 b = 0,这就与题设不符了)

所以 2a % [(2+k)a+r] = 2a ≠0;

所以假设不成立；

证毕；

情况③：（证明待给出）

(3.1)假设 s串 由长度为 a 的串循环 k 次构成：

len = k*a , next[ len ] = (k-1)*a;

len – next[len] = a , len / (len – next[len] = k;

所以可得循环次数为 k;

(3.2)

……………………..

---

KMP求字符串循环节的应用：

给出一字符串 s，求出最少需要增加多少字符使得字符串 s 变成循环次数 ≥ 2 的串？

1.如果 len%(len-nex[len]) == 0 && nex[len] != 0 ，答案为 0;

2.如果 2*next[len] < len，答案为 len-2*nex[len];

3.如果 2*next[len] ≥ len，设 k = len-next[len]，那么答案为 k-len%k;

我的理解：（ps：图片中出现的字母全为相应子串的长度）

情况1显而易见；

情况2对应的字符串如下图所示：

字符串s的最长公共前缀与最长公共后缀不重合，那么最少需要增加 b 个字符，形成 abab 类型的循环串；

b = len – 2*next[len];

情况3对应的字符串如下图所示：

字符串s的最长公共前缀与最长公共后缀重合，重合长度为 b，那么只需在 x 后补充字符 s[ x,x+1,…,a-1 ] 便可构成循环节为

s[ 0,…..,a-1 ] 的循环串，此时最少需要增加 a-x 个字符；

b = 2*next[len] – len;

a = next[len]-b = len-next[len];

x = len%a;

a-x = a-len%a;