字符串匹配 – KMP 算法
KMP 算法 是用来在字符串中搜索一个子字符串的算法。
本文内容较多,需要读者静心阅读。
在长度为 n
的字符串 s
中搜索长度为 m
的子串 p
的位置。
本文以 ABCDABCABCABABCABCDA
为主串 , ABCABCD
为子串。
易知,简单匹配方法如下:
- 将子串
p
依次对齐到s
的每个字符的位置。 - 迭代子串进行比对,如果全部匹配,则完成匹配。
此方法的代码省略,其时间复杂度是 $O(m * n)$ 。
将上面简单匹配的过程展开,如下图 1.1 所示,其中绿色的部分表示字符比对成功,红色表示比对失败 。 图中每一次比对,都会将子串 p
右移一位,然后子串从头开始匹配。
下面将考虑如何减少比对的次数。
考虑第一次失配的状态,如下图 1.2 所示,此时绿色的部分是目前匹配成功的部分。
将说明,接下来的两次比对,可以跳过。
原因在于,右移后的重叠部分 overlap
都无法匹配,整个子串 p
就不必比对了。
下面考虑第二次失配的状态,如下图 1.4 所示,同样的思路可以知道,中间的两次比对可以跳过。
原因仍然在于,因为重叠部分 overlap
无法匹配,整个子串 p
必然无法匹配。
但是,下面一次移动,就无法如此断言。因为重叠部分 overlap
是匹配的,意味着尾端的 ABC
有可能作为下一次比对的开头,那么有必要进行进一步的比对。
以上所说的重叠部分 overlap
是什么?
在刚刚失配时,假设已经匹配成功的部分是 p'
,它是 p
的一个子串, 那么重叠部分是 p'
尾部 和 右移 p'
后的头部交叉:
如果 p'
的尾部和头部是无重叠的,则可以开心地跳跃 len(p')
个字符。否则,如果 p'
的尾巴和头有匹配的部分,假如匹配了 len(overlap)
个字符, 那么只可以向右跳跃 len(p') - len(overlap)
个字符。
按照这个结论,算法过程优化为下图的样子:
此外,因为重叠部分 overlap
已经是匹配的,所以,移动 p
后,不必回溯到 p
的起点再去匹配一次,直接从失配处继续匹配即可。
如此,最终的算法过程则是下图的样子,可以看到,主串 s
的遍历无需回溯,只需要在失配的时候回溯子串就好了。
而子串回溯时, j
应该跳到的位置,恰好可以用已经匹配好的子串 p'
的头尾重叠部分的长度 len(overlap)
来表达:
接下来讨论,如何求解重叠部分的长度。
现在的问题是,对于子串 p
的每一个前缀子串 p'
,如何找到它的头部和尾部的重叠部分的长度?
我们观察一下本文例子中的 p'
的情况和对应的 overlap
长度。 下图 2.1 中左边的是 p
的每一个前缀子串,右边是头尾重叠部分的长度:
采用归纳法分析, 假设 p'(k)
表示长度为 k
的子串,其重叠部分长度为 len(k)
。 我们考虑对它的右面新增一个字符,形成新的子串 p'(k+1)
:
-
如果新增的字符和原来重叠部分后的字符相同,那么:
len(k+1) = len(k) + 1
,如下图 2.2 所示: -
否则,新的子串没有形成头尾重叠,
len(k+1) = 0
。
其中,用来和新增的字符对比的元素 (上图 2.2 和 2.3 中的 左边的 C
)的位置,是 len(k)
,对应的元素为 p'(k)[len(k)]
。
这样就形成了递推关系,这里所说的 len(k)
就是常说的 next
数组,它指明了失配时,子串回溯的目标位置。
从算法的总体过程可以看出:
-
预处理过程
共有
m
个前缀子串,因此时间复杂度O(m)
。 -
查找过程
由可知,查找过程的迭代次数 =
i
迭代次数 + 失配次数。因为主串不回溯,失配时,j
回溯后会再原地匹配一次。 即n + 失配次数
小于2n
。
总体的时间复杂度则为 O(2n + m)
即 O(n + m)
,因 m < n
,也可说时间复杂度是 O(n)
。
// ComputeNext 为长度为 m 的模式串 p 计算 next 数组. // next 数组的含义: // 取字符串 p 的位置 j 之前的前缀字符串 p' ,其头尾的最大公共长度即 next[j] // 此处采用递推方法实现 void ComputeNext(char *p, int m, int next[]) { next[0] = 0; if (m <= 1) return; // p' 是单个字符时,认为它无公共头尾 next[1] = 0; // j 是 next 数组的第 j 项 // p' 是字符串 p 的长度为 j 的子串 int j = 2; while (j < m) { if (p[j - 1] == p[next[j - 1]]) { next[j] = next[j - 1] + 1; } else { next[j] = 0; } j++; } }
// KMP 从长度为 n 的字符串 s 中查找长度为 m 的字符串 p ,返回其位置. // 找不到则返回 -1 int KMP(char *s, int n, char *p, int m) { // 预处理 next 数组 int next[m]; ComputeNext(p, m, next); // i 遍历 s // j 遍历 p int i = 0; int j = 0; while (i < n) { // 匹配 if (s[i] == p[j]) { if (j == m - 1) { // 子串匹配到尾部,说明命中 // 返回匹配的起始位置 return i + 1 - m; } else { // 否则,则继续匹配 i++; j++; } } else { if (j == 0) { // j 已经在串首, 说明第一个字符不匹配 // 不必再回溯子串,主串迭代进 1 i++; } else { // 失配,j 回溯 // 回溯的目标位置,已经匹配到的子串的头尾公共部分的长度处 j = next[j]; } } } return -1; // 查找失败 }
(完)