KMP算法

KMP算法

因为教材基本都是把1作为串的开始索引计算，而本人觉得string的索引是从0开始的，本文全片以串的索引为0开始，说明算法。

一、朴素模式匹配算法

在 “helloworld” 中匹配 “llo”，匹配成功时的指针状态。

朴素模式匹配算法的实现代码：

int Index(string str, string subStr){ int cur = 0; int j = 0; int i = cur; while(j < subStr.size() && cur < str.size()){ if(str[i] != subStr[j]){ cur++; // 主串当前遍历的位置后移 i = cur; // 不相等，开始找下一个字串 j = 0; // 子串的索引j还原，准备下一轮匹配 }else{ i++; j++; } } return j >= subStr.size() ? cur : -1;}

算法缺点： 一旦进行 指针i 和 指针j 指向的字符不同，指针i 就得退回到指针cur的地方，等待下一轮匹配。若在匹配过程中，指针i 经常性的回溯，算法效率就会很低。

二、KMP算法

参考：​​如何更好地理解和掌握 KMP 算法?​​

KMP回溯

快速求next数组

首先说一句：快速构建next数组，是KMP算法的精髓所在，核心思想是“P自己与自己做匹配”。　　 为什么这样说呢？回顾next数组的完整定义：定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。

next[x] 定义为： P[0]~P[x] 这一段字符串，使得k-前缀恰等于k-后缀的最大的k.　　 这个定义中，不知不觉地就包含了一个匹配——前缀和后缀相等。接下来，我们考虑采用递推的方式求出next数组。如果next[0], next[1], … next[x-1]均已知，那么如何求出 next[x] 呢？

来分情况讨论。首先，已经知道了 next[x-1]（以下记为now），如果 P[x] 与 P[now] 一样，那最长相等前后缀的长度就可以扩展一位，很明显 next[x] = now + 1. 图示如下。

刚刚解决了 P[x] = P[now] 的情况。那如果 P[x] 与 P[now] 不一样，又该怎么办？

如图。长度为 now 的子串 A 和子串 B 是 P[0]~P[x-1] 中最长的公共前后缀。可惜 A 右边的字符和 B 右边的那个字符不相等，next[x]不能改成 now+1 了。因此，我们应该缩短这个now，把它改成小一点的值，再来试试 P[x] 是否等于 P[now]

now该缩小到多少呢？显然，我们不想让now缩小太多。因此我们决定，在保持“P[0] ~ P[x-1]的now-前缀仍然等于now-后缀”的前提下，让这个新的now尽可能大一点。 P[0]~P[x-1] 的公共前后缀，前缀一定落在串A里面、后缀一定落在串B里面。

换句话讲：接下来now应该改成：使得 A的k-前缀等于B的k-后缀 的最大的k.　　 您应该已经注意到了一个非常强的性质——串A和串B是相同的！B的后缀等于A的后缀！因此，使得A的k-前缀等于B的k-后缀的最大的k，其实就是串A的最长公共前后缀的长度 —— next[now-1]！

来看上面的例子。当P[now]与P[x]不相等的时候，我们需要缩小now——把now变成next[now-1]，直到P[now]=P[x]为止。P[now]=P[x]时，就可以直接向右扩展了。

vector get_next(string mode_str) { vector next(mode_str.size()); int j = 0; // 前缀末尾 next[0] = 0; for (int i = 1; i < mode_str.size(); i++) { // i指向后缀末尾 while (j > 0 && mode_str[j] != mode_str[i]) { j = next[j - 1]; } if (mode_str[j] == mode_str[i]) { j++; } next[i] = j; } return next;}int strStr(const string& str, const string& mode_str) { if(mode_str.size() == 0){ return 0; } vector next = get_next(mode_str); int j = 0; // 指向mode_str for (int i = 0; i < str.size(); i++) { while (j > 0 && mode_str[j] != str[i]) { j = next[j - 1]; } if (mode_str[j] == str[i]) { j++; } if (j == mode_str.size()) { return i - mode_str.size() + 1; } } return -1;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。