字符串匹配之KMP算法

问题

字符串匹配:判断一个较短的字符串(模式串)在一个较长字符串(主串)中是否出现或者出现的最小位置。string 里的 find 函数和文本编辑器里的查找都是字符串匹配问题。

最容易想到的方法是,遍历主串中所有可能的长度等于模式串的子串。这种算法的时间复杂度为O(mn)。

KMP是一种更快的算法,它的时间复杂度是O(m+n)。

KMP 算法

假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

KMP的匹配过程其实很简单,这里主要是要求出next数组,next数组只与模式串有关,需要经过前期的预处理得到。

next 数组的作用是,某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到哪个位置。

next 数组等同于,当前字符之前的字符串中,有多大长度的相同前缀后缀。例如如果next [j] = k,代表j 之前的字符串中有最大长度为k 的相同前缀后缀。

最长前缀后缀

最长前缀后缀很好理解,可以用来求解next数组。

最长前缀后缀就是,最大的k,使得字符串前面的k个字符和后面的k个字符分别相等。

举例:字符串ABCDABD和它的各个前缀的最长前缀后缀分别为:

模式串 A B C D A B D
最大前缀后缀 0 0 0 0 1 2 0

next 数组相当于“最大前缀后缀值” 整体向右移动一位,然后初始值赋为-1

所以字符串ABCDABD的next数组如下:

模式串 A B C D A B D
next -1 0 0 0 0 1 2

next数组的计算

当前next数组的值可以根据前面已求得的值得到,类似于动态规划。

现已知next [0, …, j],如何求出next [j + 1]呢?

next[j] = k 代表p[j] 之前的模式串子串中,有长度为k 的相同前缀和后缀。

看代码会更清楚:

void get_next(string pattern, int next[])
{
	int m = pattern.length(), k;
	next[0] = -1;
	for (int i = 1; i < m; i++)
	{
		k = next[i - 1];
		while (k >= 0)
		{
			if (pattern[k] == pattern[i - 1])
				break;
			else
				k = next[k];
		}
		next[i] = k + 1;
	}
}

KMP实现

#include <iostream>
#include <string>
using namespace std;
void get_next(string pattern, int next[])
{
	int m = pattern.length(), k;
	next[0] = -1;
	for (int i = 1; i < m; i++)
	{
		k = next[i - 1];
		while (k >= 0)
		{
			if (pattern[k] == pattern[i - 1])
				break;
			else
				k = next[k];
		}
		next[i] = k + 1;
	}
}

//check whether target string contains pattern 
bool KMP(string pattern, string target)
{
	int m = pattern.length();
	int n = target.length();
	int *f = new int[m];

	get_next(pattern, f);
	int i = 0;
	int k = 0;
	while (i < n)
	{
		if (k == -1)
		{
			i++;
			k = 0;
		}
		else if (target[i] == pattern[k])
		{
			i++;
			k++;
			if (k == m)
			{
				delete[] f;
				return 1;
			}
		}
		else
			k = f[k];
	}

	delete[] f;
	return 0;
}

int main()
{
	string tar = "san and linux training";
	string pat = "lin";
	if (KMP(pat, tar))
		cout << "'" << pat << "' found in string '" << tar << "'" << endl;
	else
		cout << "'" << pat << "' not found in string '" << tar << "'" << endl;
	pat = "sanfoundry";
	if (KMP(pat, tar))
		cout << "'" << pat << "' found in string '" << tar << "'" << endl;
	else
		cout << "'" << pat << "' not found in string '" << tar << "'" << endl;
	return 0;
}