本文适合以前学过KMP算法、想要温习和加深理解的读者阅读，不适合作为初学材料。
传统的字符串匹配算法
在传统的字符串匹配算法中，不论主字符串（T）和模式串（P，亦即关键字）已经匹配了多少位字符，只要T[i]和P[j]不相符，就得回炉重造倒回重新匹配，j和i都需要回溯。
但事实上，在T和P逐步匹配的过程中，我们完全可以得到一些有效的、可以避免重复工作的数据——
KMP
比如T的前5位和P的前5位已经匹配成功，在第6位时匹配失败，那么如果说在P的前5位（假设是ABCAB）里，有一个k值，使前k位和后k位的字符串可以相匹配（在这个例子里，k=2，前2位和后2位的字符串都是AB），则在 “T的前5位和P的前5位已经匹配成功” 的前提下，我们就可以不移动i，并且不必将j重设为0，而使j=k（指向k位字符串后的第一位，在这个例子中，即指向‘C’）。
这也就是KMP算法的核心思想。
注意，这里保持了i始终不回溯，但最终要求的结果（字符串P在T中首先出现的位置）是i-j。也就是说，如果单独把结果res当做一个变量的话，res是可能会回溯的。
于是KMP算法可以概括为：
不回溯T的i指针，在i和j不匹配的情况下将j重设为k。 k值由进行匹配之前对P字符串的计算得到，存储在数组next[p.length()]里。
代码
#include<iostream>
#include<string>
using namespace std;
int* GetNext(const string& p){
int lenp = p.length();
int*res = new int[lenp];
int k = 0;
*(res+0) = 0;
if (lenp > 1)*(res+1) = 0;
for (int i = 1; i < lenp-1; i++){
if (p[i] == p[k])*(res+i+1) = ++k;
else {
*(res+i+1)= 0;
k = 0;
}
}
return res;
}
void FindPosition(const string& t,const string& p){
int pos;
int lent = t.length();
int lenp = p.length();
int* next = new int[lenp];
next = GetNext(p);
//get ks
bool suc = false;
int j = 0;
for (int i = 0; i < lent; ){
if (t[i] == p[j]){
if (j == lenp - 1){
suc = true;
pos = i-j+1;
break;
}
else{
i++; j++;
}
}
else{
if (j == 0)i++;
else j = next[j];
}
}
//print result
if (suc){
cout << p << " is found at position " << pos << endl;
}
else{
cout << "Not found." << endl;
}
}
int main(){
string t, p;
cin >> t >> p;
FindPosition(t, p);
system("pause");
return 0;
}
这是我撸的渣代码，和教科书上简洁而优美的代码当然有云泥之别，甚至可能还有bug。
但就基本思路而言，与这段代码的冗长所共生的直白逻辑也许更让人易于理解，故在此贴上，聊作对前文不走心的解释的补偿。
最后再附上简洁而优美的教科书代码。
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}