字符串匹配之KMP算法
问题
字符串匹配：判断一个较短的字符串（模式串）在一个较长字符串（主串）中是否出现或者出现的最小位置。string 里的 find 函数和文本编辑器里的查找都是字符串匹配问题。
最容易想到的方法是，遍历主串中所有可能的长度等于模式串的子串。这种算法的时间复杂度为O(mn)。
KMP是一种更快的算法，它的时间复杂度是O(m+n)。
KMP 算法
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [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 的相同前缀和后缀。
- 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
- 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[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;
}