关于KMP算法的理解

最近研究一块内容,需要先熟悉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

  • 《算法导论》
Kai Su /
Published under (CC) BY-NC-SA in categories Algorithms  tagged with kmp