网站设计一般是什么专业,国内信息图制作网站,服装公司网站定位,宁波哪里有网站建设高端的KMP 算法是一种字符串匹配算法。字符串匹配算法的目标是#xff1a;在字符串 s 中找到与模式串 p 相等的子串#xff0c;输出其位置。例如#xff1a;s “abcdef”#xff0c;p “cdef”#xff0c;p 在 s 中的位置是 2#xff08;从 0 开始计数#xff09;。 容易想到…KMP 算法是一种字符串匹配算法。字符串匹配算法的目标是在字符串 s 中找到与模式串 p 相等的子串输出其位置。例如s “abcdef”p “cdef”p 在 s 中的位置是 2从 0 开始计数。 容易想到的方式就是暴力算法。 int findString(string s, string p) {int n s.size(), m p.size();int i, j;for (i 0; i n - m 1; i) {for (j 0; j m; j) {if (s[i] s[j]) continue;break;}if (j m) return i;}return -1;}暴力算法的最坏情况下时间复杂度是 O ( n m ) O(nm) O(nm)。而本文尝试要讲明白的 kmp 算法他的摊还时间复杂度是 O ( n ) O(n) O(n) 的。 kmp 算法执行速度要快不少但是也是有代价的也就是出了名的难理解。但我认为只要 提纲挈领的找到 kmp 算法的主干那还是比较好理解的也就 2 分钟的事吧。算法实现上会有一些坑这才是最难的地方需要将里面的思路捋顺但花些时间总能搞出来。那我们就开始吧。
从直觉开始
假设有这样一个样例s “bacbababababcbab”p “ababaca”。算法运行到如下位置时匹配错误了。 暴力算法会移进 1 字符然后重新从 s 的 5 号字符和 p 的 0 号字符开始匹配。相当于 s 的索引回退到 5p 的索引回退到 0。 而 kmp 算法就比较聪明一些。既然 p 字符串的 0 到 4 号元素都匹配成功了我们何不利用这个信息多向前移动几个字符呢怎么做呢 kmp 算法的思想如下到目前位置已经成功匹配了 p 的前缀中 “ababa” 这个字符串。然后我们同时考虑它的 前缀 和 后缀会发现 它的前三个字符和后三个字符是完全一样的。所以我们完全可以向下图一样从 s 的 9 号 字符和 p 的 3 号字符开始匹配相当于 s 的索引没有回退p 的索引回退到 3。这可比暴力匹配回退的少多了因此也就快多了。 至此 kmp 算法的思想就讲完了。上述思想如果不考虑如何实现的话可能最多 2 分钟就可以理解。 但是想要实现它却又不知该怎么下手那我们就一点一点的拆解它。
next 数组引入
next 数组往往又叫前缀函数。我们不整那么高深的东西就为了解决一个问题p 的索引该回退到哪 根据上面的分析s 的索引是没有回退的那么 p 的索引该回退到哪里呢这个问题需要再精确一些如果 p 在 索引 i 的位置匹配失败了那么 p 的索引该回退到哪里这就是 next 数组的作用索引应该回退到 next[i] 的位置。 为了不使代码复杂化我们先假设如果已经得到了 next 数组算法框架是什么样的呢
版本1 int findString(string s, string p) {int n s.size(), m p.size();int i, j 0;for (i 0; i n;) {if (s[i] p[j]) { // 如果相等i 和 j 都进 1i, j;} else { // 如果不相等i 保持不变j 变为 next[j]j next[j];}// 如果 j m 表示 s 在 i 处匹配完成了返回 i - m;if (j m) return i - m;}return -1;}根据版本一的注释看起来好像没什么问题但不幸的是它有 bug。j next[j] 这一行没有处理边界情况即当s[i] 不等于 s[j]并且当 j 0 时意味着 0 号位置也匹配失败了这时候 next[j] 应该等于多少呢答案是还是 0。为什么呢即使 0 号位置匹配失败了下一次应该是要把 s 的索引加 1而 p 的索引依旧是 0 才对。于是有了下面的代码版本。 plus. 有一些别的 kmp 算法版本 定义为 -1。实际上是把整个 next 数组做了一次变换只要改一下 next 数组的定义即可。我们学会一个就好了。
版本2.1 int findString(string s, string p) {int n s.size(), m p.size();int i, j 0, flag 0;for (i 0; i n;) {if (s[i] p[j]) { // 如果相等i 和 j 都进 1i, j;} else { // 如果不相等i 保持不变j 变为 next[j]j next[j];if (flag 1) {flag 0;i;} else if (j 0) flag 1;}// 如果 j m 表示 s 在 i 处匹配完成了返回 i - m 1;if (j m) return i - m;}return -1;}版本2.1是一个正确的版本但是不够优雅。作为一个程序员要有一定的审美版本 2.1 本质上是用单层循环模拟了多层循环如果能够拆出来就更好了。 版本2.2 int n s.size(), m p.size();int i, j 0;for (i 0; i n; i) {// 如果不相等i 保持不变j 变为 next[j]while (j ! 0 s[i] ! p[j]) {j next[j];}if (s[i] p[j]) { // 如果相等j 进 1j;}// 如果 j m 表示 s 在 i 处匹配完成了返回 i - m 1;if (j m) return i - m 1;}return -1;}嗯版本2.2 就优雅许多了。
next 数组生成
那么 next 数组该如何生成呢 对照这幅图当 p 的 5 号索引匹配失败是j 应该跳转到 3 号。可以观察到next[i] 表示 [0, i - 1] 区间表示的字符串 p i p_i pi 中 重叠的前缀与后缀的最长值 k并且 k 要小于 p i p_i pi 的长度因为自己等于自己可不算。 所以算法如下 vectorint next(m, 0);for (int i 2; i m; i) { // 前两个数字默认为 0int t next[i - 1]; // 前面的前面的那个区间有最长多少个重叠的前后缀// 前面的区间末尾 和 前面的前面的区间的末尾如果不相等就一直 next// 这点和匹配算法很像while (t ! 0 p[i - 1] ! p[t]) { t next[t];}next[i] t;if (p[i - 1] p[t]) next[i] t 1; //如果相等就 1}合成如下 int strStr(string s, string p) {int n s.size(), m p.size();// 求 next 数组vectorint next(m, 0);for (int i 2; i m; i) {int t next[i - 1];while (p[i - 1] ! p[t] t ! 0) t next[t];if (p[i - 1] p[t]) t;next[i] t;}// 匹配int j 0;for (int i 0; i n; i) {while (s[i] ! p[j] j ! 0) j next[j];if (s[i] p[j]) j;if (j m) return i - m 1;}return -1;}总结
kmp 算法思想就是使用已匹配的前缀字符串从中抽取出前后缀的重叠部分信息用以减少字符串匹配中的回退从而达到加速的作用。其实现有两个坑一个是next 数组含义的准确定义(我的定义应该和书上不一样)第二个坑就是使用内循环来多次使用 next 数组跳转。其中第二个坑相信大家自己写都能意识到第一个坑才是决定你能不能写出来的关键因素。我的实现可能不是最好的但是希望能够好懂一点。
kmp 算法已将前缀信息使用到了极致还有一些别的字符串比较算法要比 kmp 容易一些比如 sunday 算法等。还有一些算法可能比 kmp 还要复杂一些使用到了后缀信息例如bm 算法。还有 一个 RK 算法使用哈希字符串的方式简单易写。这些算法有机会再说吧。
