KMP算法是一种改进的字符串匹配算法，关键是利用匹配后失败的信息，尽量减少模式串（W）与主串（T）的匹配次数以达到快速匹配的目的。具体实现就是实现一个next() 函数，函数本身包含了模式串的局部匹配信息。时间复杂度 O(m+n)。
如果考虑一般的方法，我们可以将T[0]和W[0]进行匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1]跟W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，时间复杂度为O(m*n)。
学习代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//get_next函数
vector<int> get_next(string b) //用vector来保存子串b的next数组
{
vector<int> result; //添加元素并且默认赋值为0，建立一个空的容器就
int i, j;
i = 0;
j = -1;
result.push_back(-1); //将容器首元素赋值，作为标识使用
while (i < b.size() - 1)
{
if (j == -1 || b[i] == b[j]) //b[i]表示后缀的单个字符，b[j]表示前缀的单个字符
{
++i;
++j;
//这里的其实是优化重复的字符
//可以直接用result.push_back(j);代替下面的判断语句
if (b[i] != b[j])
result.push_back(j);
else if (i == 1)
result.push_back(j);
else
result.push_back(result[j]);
}
else
j = result[j]; //若字符不同，前缀字符回溯
}
return result;
}
//KMP函数
int KMP(string a, string b)
{
vector<int> next = get_next(b); //调用get_text函数
int i = 0;
int j = 0;
//注意size函数返回的类型是string::size_type是无符号数
//若i<主串的长度且j<子串的长度时，循环继续
while (i < (int)a.size() && j <(int)b.size())
{
if (j == -1 || a[i] == b[j]) //两字母相等则继续，相对于朴素算法增加了
{
++i;
++j;
}
else {
j = next[j]; //若不相等，j退回合适的位置
}
}
if (j == b.size())
{ //这里返回的是匹配字符开始的下标位
return i - j;
}
else {
return -1;
}
}
int main()
{
string str;
cout << "enter the string:";
cin >> str;
string pattern;
cout << "enter the pattern:";
cin >> pattern;
int result = KMP(str, pattern);
cout << result << endl;
}