朴素匹配的过程中存在回溯，也就是说当匹配过程中出现t[i]与p[j]不等时，其实t[i-j]~t[i-1]与p[0]~p[j-1]是已经匹配相等的，然而朴素匹配没有利用这部分的匹配过程，造成了时间资源的浪费。我们希望能够设计出算法，其在匹配过程中没有回溯，同时又不丢失任何匹配成功的机会。
快速匹配KMP实现的细节有较多的版本，这边我采用的思路是：t串和p串匹配过程中出现p[i]和t[j]不相等时，用p中以next[i]为下标的字符p[next[i]]与t[j]比较，若p中任何字符都不必再与t[j]比较，则直接从t[j+1]和p[0]开始比较，对于任何模式p，只要能确定next[i]（i=0…len_p-1），就可以实现快速匹配，当p[i]!=t[j]时，直接右移i-next[i]个字符，若next[i]>=0，则t[j]与p[next[i]]继续比较，否则从t[j+1]与p[0]继续比较，理解透彻需要花一点时间，实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35// 快速匹配函数
int pMatch(char* p,char* t,int len_p,int len_t){
// t是目标串，p是模式串
int i,j; // i记录p的当前匹配位置，j记录t
i=0 ;j=0; // initialize
while( i<len_p && j<len_t){
//循环停止条件：模式串能正确匹配到串末或目标串匹配结束，匹配失败
if(p[i]==t[j]||i==-1){ // 考虑next[i]为-1的情况
++i;++j; // 继续向后匹配
}else{//下次匹配时，t串从匹配失败的字符开始，p串从next[i]的位置开始
i=next[i];
}
}
if(i>=len_p) return j-len_p+1; // 匹配成功，返回p[0]在t中的位置
else return 0;
}// next[i]存放的是p[0]...p[i-1]这个字符串中最长相同前后缀子串的长度
执行过程中，j只增不减，j++最多执行len_t次，i++语句最多执行也不超过len_t次，时间代价O(len_t)
快速匹配的关键在next数组的计算：
// 计算next[]数组
void makeNext(char* p,int len_p,int* next){
int i=0,k=-1; // i指向p当前字符，k是记录next数组中元素的值
next[0]=-1; // p[0]和t[j]比较不相等，下次仍从p[0]开始比较
while(i < len_p-1 ) { // 计算next[i+1]
while(k>=0 && p[i]!=p[k]) // next[i]<i,next[k]是p[0]...p[k]最长相同前后缀计算
k=next[k];
i++;k++;
next[i]=k;
/*
if(p[i]==p[k]) next[i] = next[k];
else next[i]=k;
*/
}
}
每执行一次外层循环，i严格增1，故外层循环正好执行len_p-1次，k的值从-1开始k+len_p-1次，并且只有在这一语句中k被增值。在内层循环中，k=next[k]至少使k减少1，所以整个算法中该语句执行次数累计不超过len_p-1次，故内层循环总执行次数最大为m-1。计算next数组的执行时间是O(len_p)。算法总计算时间为O(len_p_+len_t)，相比暴力优化了很多。
