kmp算法复杂度o m?希尔排序算法?KMP算法学习总结(2)

相比较。

4、kmp算法的实现

在已知next函数的前提下，根据上面的步骤，kmp算法的实现如下：

int kmp(const std::string& s, const std::string& p, const int sIndex = 0) { std::vector<int>next(p.size()); getNext(p, next);i = sIndex, j = 0; while(i != s.length() && j != p.length()) { if (j == -1 || s[i] == p[j]) { ++i; ++j; } else { j = next[j]; } } return j == p.length() ? i - j: -1; }

ok，下面的问题是怎么求模式串 P 的next数组。

next数组的初始条件是next[0] = -1，设next[j] = k，则有：

那么，next[j+1]有两种情况：

此时next[j+1] = next[j] + 1 = k + 1

， 如图所示：

此时需要将P向右滑动之后继续比较P中index为 j 的字符与index为 next[k] 的字符：

值得注意的是，上面的“向右滑动”本身就是一个kmp在失配情况下的滑动过程，将这个过程看 P 的自我匹配，则有：

，则next[j+1] = next[k] + 1；

否则，继续将 P 向右滑动，直至匹配成功，或者不存在这样的匹配，此时next[j+1] = 0。

getNext函数的实现如下：

void getNext(const std::string &p, std::vector<int> &next) { next.resize(p.size()); next[0] = -1; int i = 0, j = -1; while (i != p.size() - 1) { (j == -1 || p[i] == p[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } }

至此，一个完整的kmp已经实现。

5、getNext函数的进一步优化

注意到，上面的getNext函数还存在可以优化的地方，比如：

i=3

S: a a a ba aa a b

P:a aa ab

j=3

此时，i=3、j=3时发生失配，next[3]=2，此时还需要进行 3 次比较：

i=3, j=2;

i=3, j=1;

i=3, j=0。

而实际上，因为i=3, j=3时就已经知道a!=b，而之后的三次依旧是拿 a 和 b 比较，因此这三次比较都是多余的。

此时应当直接将P向右滑动4个字符，进行 i=4， j=0的比较。

一般而言，在getNext函数中，next[i]=j，也就是说当p[i]与S中某个字符匹配失败的时候，用p[j]继续与S中的这个字符比较。

如果p[i]==p[j]，那么这次比较是多余的（如同上面的例子），此时应该直接使next[i]=next[j]。

完整的实现代码如下：

void getNextUpdate(const std::string& p, std::vector<int>& next) { next.resize(p.size()); next[0] = -1; int i = 0, j = -1; while (i != p.size() - 1) { (j == -1 || p[i] == p[j]) { ++i; ++j; //update //next[i] = j; //注意这里是++i和++j之后的p[i]、p[j] next[i] = p[i] != p[j] ? j : next[j]; } else { j = next[j]; } } }

对应的，只需要在kmp算法中将getNext(p, next); 替换成getNextUpdate(p, next); 即可。

6、时间复杂度分析

下面以getNext函数为例，分析kmp算法的时间复杂度。

1 void getNext(const std::string& p, std::vector<int>& next) 2 { 3 next.resize(p.size()); 4 next[0] = -1; i = 0, j = -1; (i != p.size() - 1) 9 { 10 if (j == -1 || p[i] == p[j]) 11 { 12 ++i; 13 ++j; 14 next[i] = j; 15 } { 18 j = next[j]; 19 } 20 } 21 }

假定p.size()为m，分析其时间复杂度的困惑在于，在while里面不是每次循环都执行 ++i 操作，所以整个while的执行次数不一定为m。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-8680-2.html