最近研究一块内容,需要先熟悉KMP算法。查阅些资料,觉着还是算法导论讲解地最为清晰。
一. 理论基础
算法导论是从最朴素的字符串匹配算法开始的。
T表示文本串,P表示模式串。当前例子显示q=5个字符成功匹配,第6个字符匹配失败。此时需要向右偏移模式串P,继续匹配。然而如果朴素地将当前偏移s仅仅增加一个偏移,即s+1,这个操作是无效而且有些浪费。因为此时模式的第一个字符(a)不能和文本的第二个字符(b)匹配,无效地偏移是不符合KMP算法“要求”的。若偏移2,s’=s+2能使模式串至少前三个字符和相应文本字符匹配,这是符合KMP算法“初衷”的。
那么,KMP的“要求”具体是指什么呢?
假设P[1..q]与文本T[s+1..s+q]匹配,KMP需要计算最小的偏移量s’(s’>s),对于某些k < q,满足
P[1..k] = T[s’+1..s’+k] , 其中 s’+k = s+q (一)
回到上面的图,可以发现:模式串P(1..q)是T(1..s+q)的后缀。我们希望找到P(1..q)的最长前缀P(1..k)也是T(1..s+q)的后缀。这样,算出最长k后,利用公式s’+k=s+q就可以算出最小偏移s’了。
所以,KMP目的是预先计算某些“信息”,计算s’,避免一些无效偏移的匹配。
而且,我们可以利用模式串和其自身比较来预先计算这些信息。通过上图可以看出,T[s’+1..s’+k]是P(1..q)的一个后缀,所以可以将公式(一)解释为:
计算最大的k,使得P(1..k)是P(1..q)的后缀。(而且其实这个P(1..k)即是P(1..q)的后缀,也是P(1..q)的前缀)
形式化为:
next[q] = max{k: k < q 而且 P(1..k)是P(1..q)的后缀}
二. 流程图及代码实践
画个草稿流程图可以很好理解(注:为了方便,上面理论基础部分字符串从1开始计数,实际代码编写则从0开始计数)
着重理解计算next数组时k = next[k - 1]
的含义。
vector<int> buildNext(string pattern) {
size_t m = pattern.length();
vector<int> next(m, 0);
int k = 0;
// 首先, next[0] = 0, 所以q直接从1开始遍历
for (size_t i = 1; i < m; i++) {
while (k > 0 && pattern[k] != pattern[i])
k = next[k - 1]; //或者k--;
if (pattern[k] == pattern[i])
k++;
next[i] = k;
}
return next;
}
vector<int> KMP(string text, string pattern) {
vector<int> matchPoints;
vector<int> next = buildNext(pattern);
size_t m = pattern.length(), n = text.length();
int k = 0;
for (size_t i = 0; i < n; i++) {
while (k > 0 && pattern[k] != text[i])
k = next[k - 1];
if (pattern[k] == text[i])
k++;
if (k == m) {
matchPoints.push_back(i);
k = next[k - 1];
}
}
return matchPoints;
}
References
- 《算法导论》