KMP算法是一种改进的
字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为
克努特——
莫里斯——
普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。
时间复杂度O(m+n)。
设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b
模式串（下文中我们称作W）为：a b a c a b
用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。
而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在
已经匹配的模式串子串中，找出最长的相同的
前缀和
后缀，然后移动使它们重叠。
在第一次匹配过程中
T: a b a c a
a b a c a b a c a b a a b b
W: a b a c a
b
在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的
已经匹配的模式串子串，现在移动找出
最长的相同的前缀和后缀并使他们重叠：
T: a b a c a
a b a c a b a c a b a a b b
W: a
b a c a
b
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
然而，如果每次都要计算
最长的相同的前缀反而会浪费时间，所以对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间就成了常数时间。比如：
| j |
0 |
1 |
2 |
3 |
4 |
5 |
| W[j] |
a |
b |
a |
c |
a |
b |
| F(j) |
0 |
0 |
1 |
0 |
1 |
2 |
当W[j]与T[j]不匹配的时候，设置j = F(j-1).
C++源代码：
#include
#include
#include
using namespace std;
inline void NEXT(const string&T, vector&next){//按模式串生成vector,next(T.size())
next[0] = -1;
for (int i = 1; i= 0 && T[i - 1] != T[j]) j = next[j];//递推计算
if (j >= 0 && T[i - 1] == T[j]) next[i] = j + 1;
else next[i] = 0;
}
}
inline string::size_type COUNT_KMP(const string&S, const string&T){
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vectornext(T.size());
NEXT(T, next);
string::size_type index, count = 0;
for (index = 0; index> S;
//cin >> T;
string::size_type count = COUNT_KMP(S, T);
cout <
京公网安备 11010802041100号