浅析KMP算法（附C++源码）
模式匹配问题在字符串中很常见，我们常用KMP算法来解决模式匹配问题，下面将浅析KMP算法
目录
起源
给出一个比较长的字符串S，另外给出一个较短的字符串W，探索W是不是S的子串，或者是探索W是否在S中出现过，如果出现过，出现了多少次，分别在S中的哪个位置。
一般我们都会直接从S[0]与W[0]比较，如果相等就继续比较，直到整个W完全匹配正确，如果中途出现一个不相等，就从S[1]跟W[0]相比，重复上一步。在这个循环中，每次匹配失败，都丢弃所有已经匹配过的数据，重新匹配，S的下标每次都是只增加1。KMP算法就是对这一步进行优化。
算法分析
简易KMP
正如前面所说的，每次匹配失败，所有匹配的数据都丢弃，S的下标只增加1。这样的效率很低下，举个简单的例子：
源串S=”abcabcd”，模式串W=”abcd”，开始匹配时：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| S | a | b | c | a | b | c | d |
| W | a | b | c | d |
S[3]和W[3]不相等，一般情况下我们下一步会这样做：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| S | a | b | c | a | b | c | d |
| W | a | b | c | d |
然而，从已经匹配好的”abc”子串来看，’a’只出现了一次，即S[1]，S[2]不是’a’，意味着在S[1], S[2]不可能与’a’开头的模式串W匹配，所以我们可以直接跳过S[1]和S[2]，直接从S[3]继续比较。
这就是KMP算法的简易版。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| S | a | b | c | a | b | c | d |
| W | a | b | c | d |
误区
那干脆每次匹配失败直接把S的下标向前移动一段距离，这个距离就是刚刚已经匹配成功的子串长度。如果KMP算法就这样，那么也没什么值得称颂的。事实上，这个想法有个很大的缺陷，比如下面这个例子：
S=”aaabc” W=”aab”
第一步：
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| S | a | a | a | b | c |
| W | a | a | b |
这里匹配成功的子串为“aa”，长度2，那么如果按照假定的想法来做，那么将这样：
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| S | a | a | a | b | c |
| W | a | a | b |
结果居然是：W不是S的子串。
很明显这是错误的。
完整版KMP
那么，匹配失败的时候源串S的下标该前进多少呢？
KMP算法给出了一个方案：
显然，S下标该前进的长度跟已经匹配成功的子串有关，而这个子串肯定是模式串W的子串。为模式串W构建一个表（next表）来记录在每个位置匹配失败时S前进长度的一个相关值。注意，是通过此值可以算出S的前进长度，而不是S下标前进长度本身。
这里要解释一下“真前缀和真后缀相同的最大长度”，比如，对于字符串“abcdefab”，真前缀和真后缀相同的是“a”和“ab”，则“真前缀和真后缀相同的最大长度”为“ab”的长度2。next表记录的就是该处之前子串的“真前缀和真后缀相同的最大长度”。比如：“abcdef”中，位于‘e’点next值，就是“abcd”的“真前缀和真后缀相同的最大长度”，为0。举个例子体会一下(为了方便，首位一般为-1）：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| W | a | a | b | a | a | a | c |
| next值 | -1 | 0 | 1 | 0 | 1 | 2 | 2 |
计算next表
那么该怎么用算法来算出这个next表，下面给出我的源码，里面注释挺详细，可以直接体会：
大概思路很简单，要找出前缀（后缀）的最长值，就必须记录好已经适配的前缀（前缀的下标容易处理）的位置，我用cnd保存。
两个相邻的next值，后者要算的字符串仅比前者多一个字符，只需要多出的字符和之前匹配好的前缀下一个字符(W[cnd+1])相等，就意味着，相同前缀长度增加1，后一个next值比前一个next值大1。比如W=“ababc”，中W[2]和W[3]处。
如果多出的字符和之前匹配好的前缀下一个字符（W[cnd+1]）不相等，那么cnd=next[cnd]，
（不采用cnd=0是一种优化处理，意思是虽然当前串的下一个字符不能和你（多出的字符）匹配，但是当前串的前缀和下一个字符连起来可能匹配成功，而最长相同前缀就是next[cnd]，所以cnd=next[cnd]是最优选择）
如“aabaaac”中，W[5]的next值为2，W[6]next值处理时cnd=2，“aab”和“aaa”不相等，“aa”的最长相同前缀（后缀）长度为1（即next[cnd]==1），cnd=1，再进行比较，则有“aa”相同前缀（后缀），从而得到next[6]=2;无论如何都没有相同的前缀后缀，如“abcdef”这种的，当前的next值就为0。
inline void makeNextTable(const string&W, vector<int>&next)
{
// pos是当前在模式串的位置，cnd是匹配串的位置
// 由于无论什么模式串，前两位都固定为-1和0，所以pos直接从2开始
int pos = 2;
int cnd = 0;
next[0] = -1;
next[1] = 0;
while (pos < W.size())
{
// 第一种情况：子串匹配成功，向前继续
if (W[pos - 1] == W[cnd]) // 由于要找的是pos前面的字符串的最长相同前缀后缀，所以-1
{
next[pos] = cnd + 1;
cnd++;
pos++;
}
// 第二种情况，子串匹配失败，但可以匹配到更小串，比如“aabaaa”中W[6]=2而不是1
else if (cnd > 0)
{
cnd = next[cnd];
}
// 第三种情况，子串匹配失败，且什么都匹配不了
else
{
next[pos] = 0;
pos++;
}
}
}使用next表实现KMP
有了next表，前面说这是S向前移动长度的相关值，怎么相关？
next表记录了前缀和后缀相同的最大长度，即当匹配失败的时候，
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | a | b | a | a | b | a | a | a | c | d | e |
| W | a | a | b | a | a | a | c | |||||
| next值 | -1 | 0 | 1 | 0 | 1 | 2 | 2 |
S[5]处匹配失败，此时已经匹配的子串为“aabaa”，长度为5，真前缀和真后缀相同的最长值为“aa”，长度为2（next值）。那么要将W向右移5-2=3位。（W向右移的长度就是下一轮比较开始时S的下标要前进的长度，为了方便，就说W右移）
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | a | b | a | a | b | a | a | a | c | d | e |
| W | a | a | b | a | a | a | c | |||||
| next值 | -1 | 0 | 1 | 0 | 1 | 2 | 2 |
下面是代码：
// 输出匹配成功的位置（首字母），返回值是匹配成功的次数
int countKMP(const string&S, const string&W)
{
vector<int> next(W.size());
makeNextTable(W, next);
int m = 0; // S串中匹配的第一个位置
int i = 0; // 模式串中已经匹配到的位置
int count = 0; // 匹配成功的次数
while (m+i < S.size())
{
if (W[i] == S[m + i]) { // 匹配成功
if (i == W.size() - 1) // 一次匹配完毕
{
count++;
cout << "The " << count << "th match at " << m << endl;
m = m + i - next[i];
i = next[i];
}
else // 匹配了部分，继续匹配
{
i++;
}
}
else // 匹配失败
{
if (next[i] > -1) // 虽然当前匹配失败，但是可以匹配到更小串
{
m = m + i - next[i];
i = next[i];
}
else // 完全不匹配，即从第一个字母起就不匹配了
{
m++;
i = 0;
}
}
}
return count;
}源代码
为了方便，给出一个测试程序的源代码：
/* This Algorithm is reference from the wikipedia, It is used to find the searching string in a long string. 2016-08-11 07:58:07 */
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 计算next表
inline void makeNextTable(const string&W, vector<int>&next)
{
// pos是当前在模式串的位置，cnd是匹配串的位置
// 由于无论什么模式串，前两位都固定为-1和0，所以pos直接从2开始
int pos = 2;
int cnd = 0;
next[0] = -1;
next[1] = 0;
while (pos < W.size())
{
// 第一种情况：子串匹配成功，向前继续
if (W[pos - 1] == W[cnd]) // 由于要找的是pos前面的字符串的最长相同前缀后缀，所以-1
{
next[pos] = cnd + 1;
cnd++;
pos++;
}
// 第二种情况，子串匹配失败，但可以匹配到更小串，比如“aabaaa”中W[6]=2而不是1
else if (cnd > 0)
{
cnd = next[cnd];
}
// 第三种情况，子串匹配失败，且什么都匹配不了
else
{
next[pos] = 0;
pos++;
}
}
}
// 输出匹配成功的位置（首字母），返回值是匹配成功的次数
int countKMP(const string&S, const string&W)
{
vector<int> next(W.size());
makeNextTable(W, next);
// print next表
cout << "next表:" << endl;
for (int i = 0; i < W.size(); ++i) {
if (i == W.size() - 1) {
cout << next[i] << endl;
}
else {
cout << next[i] << " ";
}
}
int m = 0; // S串中匹配的第一个位置
int i = 0; // 模式串中已经匹配到的位置
int count = 0; // 匹配成功的次数
while (m+i < S.size())
{
if (W[i] == S[m + i]) { // 匹配成功
if (i == W.size() - 1) // 一次匹配完毕
{
count++;
cout << "The " << count << "th match at " << m << endl;
m = m + i - next[i];
i = next[i];
}
else // 匹配了部分，继续匹配
{
i++;
}
}
else // 匹配失败
{
if (next[i] > -1) // 虽然当前匹配失败，但是可以匹配到更小串
{
m = m + i - next[i];
i = next[i];
}
else // 完全不匹配，即从第一个字母起就不匹配了
{
m++;
i = 0;
}
}
}
return count;
}
int main()
{
string S;// 原串
string W;// 模式串
cout << "input the origin string" << endl;
cin >> S;
cout << "intput the search string" << endl;
cin >> W;
int count = countKMP(S, W);
cout << "The times match successfully: " << count << endl;
system("PAUSE");
return 0;
}