试证KMP计算循环节方法

发表于 2021-04-27 更新于 2023-10-16 分类于 ACM

数据结构课程在string章节的实验课，多半会有循环节这道题，或许蒙的猜的或许课堂讲的，大多人会发现 strLen - next[strLen] 就是最短循环节的长度，无论是上述问题1还是问题2，都能求出循环节长度为3，即abc

但总觉得哪里怪怪的，大家都默认这样正确，在网上却不太容易找到一个严谨的证明。这篇博客试着证明一下，当然依然是非数学的，期望更容易读懂。

我们知道KMP算法的next数组是由“最长相等前后缀”推得的，strLen - next[strLen] 其实就是“字符串长度”减去“整串最长相等前后缀长度”后的长度，循环节即这个长度的前缀，这里我们就是要证明：

strLen - next[strLen] 是字符串最短循环节的长度

一个字符串的最长相等前后缀，有两种情况：

情况1：最长相等前后缀重叠

1
2
3

mmmmmmmmmmmmmm---
---mmmmmmmmmmmmmm
0  j         k  l

这里 m 表示相匹配的串

情况2：不重叠

1
2
3

mmmmm------------
------------mmmmm
0   k       j   l

对于情况1和情况2，又分别有 循环刚好填满 ，和 循环未填满需要补充 的情况。

情况`1`最长相等前后缀重叠且循环节填满

这里用 [0,k] == [j,l] 表示 0~k 的字符与 j~l 的字符顺序一一匹配，[]表示闭区间。

显然[0,j) == [j,j+j)，即最长相等前后缀之间，“前缀的前缀”肯定与“后缀的前缀”相匹配。这里)表示右侧开区间，用M来表示这个情况。

1
2
3

MMMmmmmmmmmmmmm---
---MMMmmmmmmmmmmmm
0  j          k  l

而[j,j+j) == [j+j,j+j+j) 也是成立的，最长相等前后缀之间，前缀的任意一段，等于后缀对应位移的那段，这里用P来表示

1
2
3

MMMPPPmmmmmmmmm---
---MMMPPPmmmmmmmmm
0  j          k  l

而显然，后缀的MMM和前缀的PPP是同一个区间，都是[j,j+j)，后缀的PPP又和前缀的PPP之后的长度为j的区间是同一个区间，可以连锁反应下去，直到字符串最后

1
2
3

MMMPPPOOOmmmmmm---
---MMMPPPOOOmmmmmm
0  j          k  l

可能会是这个样子

1
2
3

mmmmmmmmmmmmm---
---mmmmmmmmmmmmm
0  j        k  l

看起来没什么区别？其实就是长度不能整除这个假定的循环节了。

连锁反应还和刚才一样，最后能得到：

1
2
3

MMMPPPOOOAAAm---
---MMMPPPOOOAAAm
0  j        k  l

到这里，连锁还可以继续，后缀的AAA对应前缀的那段依然是循环，用BBB表示

1
2
3

MMMPPPOOOAAABBB-
---MMMPPPOOOAAAm
0  j        k  l

最后剩下的这个字符（或若干字符）

循环节填满字符串的话，是不可能出现情况2的

循环两次时：

1 2	AAAA---- ----BBBB

最长相等前后缀是挨着的，用情况1的连锁反应即可

循环大于两次时：

1 2	AAAACCCC---- ----BBBBCCCC

必然重叠

1
2
3

mmmmm------------
------------mmmmm
0   k       j   l

按照公式，即总长度减去最长相等前后缀长度，循环节应该是[0,j)，用M表示为

1
2
3

MMMMMMMMMMMM-----
------------mmmmm
0   k       j   l

它当作需要补齐的循环节，是符合要求的。但是否是“最小循环节”呢？

反证一下，假设有更短循环节P

1
2
3

PPPmm------------
------------mmmmm
0   k       j   l

那么，我们得到的KMP匹配结果，将会是

1
2
3

PPPAAABBBCCCDD---
---PPPAAABBBCCCDD
0   k       j   l

这是情况1而不是情况2了，产生矛盾，故不存在更小的循环节P。

几种情况都已处理完，这样可以更感性地认知strLen - next[strLen]为循环节长度的意义了。