参考
KMP 算法求解什么类型问题
字符串匹配. 给你两个字符串, 寻找其中一个字符串是否包含另一个字符串, 如果包含, 返回包含的起始位置.
如下面两个字符串:
char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";str 有两处包含 ptr, 分别在 str 的下标 10, 26 处包含 ptr.
问题类型很简单, 下面直接介绍算法.
算法说明
一般匹配字符串时, 我们从目标字符串 $\text{str}$ (假设长度为 $n$) 的第一个下标选取和 $\text{ptr}$ 长度 (长度为 $m$) 一样的子字符串进行比较, 如果一样, 就返回开始处的下标值, 不一样, 选取 $\text{str}$ 下一个下标, 同样选取长度为 $n$ 的字符串进行比较, 直到 $\text{str}$ 的末尾 (实际比较时, 下标移动到 $n-m$). 这样的时间复杂度是 $O(n*m)$.
KMP 算法: 可以实现复杂度为 $O(m+n)$
为何简化了时间复杂度: 充分利用了目标字符串 $\text{ptr}$ 的性质 (比如里面部分字符串的重复性, 即使不存在重复字段, 在比较时, 实现最大的移动量).
上面理不理解无所谓, 我说的其实也没有深刻剖析里面的内部原因.
考察目标字符串 $\text{ptr}$: ababaca, 这里我们要计算一个长度为 $m$ 的转移数组 next.
next 数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度.
比如: abcjkdabc, 那么这个数组的最长前缀和最长后缀相同必然是 abc.
cbcbc, 最长前缀和最长后缀相同是 cbc.abcbc, 最长前缀和最长后缀相同是不存在的.
注意最长前缀: 是说以第一个字符开始, 但是不包含最后一个字符. 比如 aaaa 相同的最长前缀和最长后缀是 aaa.
对于目标字符串 $\text{ptr}$, ababaca, 长度是 7, 所以
next[0] a
next[1] ab
next[2] aba
next[3] abab
next[4] ababa
next[5] ababac
next[6] ababaca由于 a, ab, aba, abab, ababa, ababac, ababaca 的相同的最长前缀和最长后缀是 "", "", "a", "ab", "aba", "", "a", 所以 next 数组的值是 [-1, -1, 0, 1, 2, -1, 0], 这里 -1 表示不存在, 0 表示存在长度为 $1$, 2 表示存在长度为 $3$. 这是为了和代码相对应.
下图中的 $1$, $2$, $3$, $4$ 是一样的. $1~2$ 之间的和 $3~4$ 之间的也是一样的, 我们发现 A 和 B 不一样; 之前的算法是我把下面的字符串往前移动一个距离, 重新从头开始比较, 那必然存在很多重复的比较. 现在的做法是, 我把下面的字符串往前移动, 使 3 和 2 对齐, 直接比较 C 和 A 是否一样.
原作者的这个图有点跳跃, 下面给出的是阮一峰画的图
一个基本事实是, 当空格与 D 不匹配时, 你其实知道前面六个字符是 ABCDAB. KMP 算法的想法是, 设法利用这个已知信息, 不要把 搜索位置 移回已经比较过的位置, 继续把它向后移, 这样就提高了效率.
怎么做到这一点呢? 可以针对搜索词, 算出一张《部分匹配表》(Partial Match Table). 这张表是如何产生的, 后面再介绍, 这里只要会用就可以了.
已知空格与 D 不匹配时, 前面六个字符 ABCDAB 是匹配的. 查表可知, 最后一个匹配字符 B 对应的 部分匹配值 为 2, 因此按照下面的公式算出向后移动的位数:
$$移动位数 = 已匹配的字符数 - 对应的部分匹配值$$
因为 6 - 2 等于 4, 所以将搜索词向后移动 4 位.
代码解析
void cal_next(char *str, int *next, int len) {
// next[0] 初始化为 -1, -1 表示不存在相同的最大前缀和最大后缀
next[0] = -1;
// k 初始化为-1
int k = -1;
for (int q = 1; q <= len-1; q++) {
// 如果下一个不同, 那么 k 就变成 next[k], 注意 next[k] 是小于 k 的, 无论 k 取任何值.
while (k > -1 && str[k + 1] != str[q]) {
// 往前回溯
k = next[k];
}
if (str[k + 1] == str[q]) {
// 如果相同, k++
k = k + 1;
}
// 这个是把算的 k 的值 (就是相同的最大前缀和最大后缀长) 赋给 next[q]
next[q] = k;
}
}KMP
这个和 next 很像, 具体就看代码, 其实上面已经大概说完了整个匹配过程.
int KMP(char *str, int slen, char *ptr, int plen) {
int *next = new int[plen];
// 计算 next 数组
cal_next(ptr, next, plen);
int k = -1;
for (int i = 0; i < slen; i++) {
// ptr 和 str 不匹配, 且 k>-1 (表示 ptr 和 str 有部分匹配)
while (k >-1 && ptr[k + 1] != str[i]) {
// 往前回溯
k = next[k];
}
if (ptr[k + 1] == str[i])
k = k + 1;
if (k == plen-1) {
// 说明 k 移动到 ptr 的最末端
// cout << " 在位置" << i-plen+1<< endl;
// k = -1; //重新初始化, 寻找下一个
// i = i - plen + 1;
// i 定位到该位置, 外层 for 循环 i++ 可以继续找下一个
// (这里默认存在两个匹配字符串可以部分重叠), 感谢评论中同学指出错误.
// 返回相应的位置
return i-plen+1;
}
}
return -1;
}测试
char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";
int a = KMP(str, 36, ptr, 7);
return 0;注意如果 str 里有多个匹配 ptr 的字符串, 要想求出所有的满足要求的下标位置, 在 KMP 算法需要稍微修改一下. 见上面注释掉的代码.
复杂度分析
next 函数计算复杂度是 $O(m)$, 开始以为是 $O(m^2)$, 后来仔细想了想, cal_next 里的 while 循环, 以及外层 for 循环, 利用均摊思想, 其实是 $O(m)$, 这个以后想好了再写上.
本文链接地址：KMP算法，英雄不问来路，转载请注明出处，谢谢。
有话想说：那就赶紧去给我留言吧。
文章评论