二) KMP算法[1977] 这里首先引入部分匹配的概念：s[k+1..k+m]与t[1..m] 有部分匹配，是指存在k+1≤i＜k+m,得s[k+1..i]=t[1..i-k]，但s[i+1]=t[i-k+1]
从朴素的模式匹配算法我们看到，不管s[k+1..k+m]与t[1..m]已实现了多长的部分匹配：s[k+1..k+j]=t[1..j],1≤j＜m,只要s[k+j+1]≠t[j+1],所得到的部分匹配都被丢弃，接着的匹配测试要回头从s[k+2]与t[1]开始。人们在为那些已得到的部分匹配被丢弃感到惋惜的同时，对部分匹配中可能隐含着有用的信息作了深入的研究。
1．分析
假设，部分匹配发生在s[k+1..i]=t[1..j]（其中0≤k≤n－m,k+1≤i＜n, 1≤j＜m, k=i-j＝,而s[i+1]≠t[j+1]。如图1所示
k k+1 k+2 l k+j-π[j]+1 i i+1
s ... .. ... ......
t ... .. ... ... ...
1 2 j-π[j]+1 π[j] j j+1
图 3.2.1
利用前缀函数的概念，对于字符串t[1..j]，它有长为π[j]的最长特别子串t[1.. π[j]],0≤π[j]＜j。
考虑s中从位置l开始的子串：
(ⅰ)当k+1≤l≤k+j-π[j]-1时，若有s[l+1..l+m]=t[1..m]，则s[l+1..i]=t[1..i－l]。但由已得到的部分匹配，有s[l+1..i]=t[j-i+l+1..j],因而有
t[1..i-l]=t[j-i+l+1..j]。……………………………………………………（3.2.1）
由于i-l≤i-k-1=j-1,（3.2.1）式表明t[1..i-l]既是t[1..j]的真前缀又是真后缀，且长度为i-l≥i-(k+j-π[j]-1)=π[j]+1,比π[j]还长。这与π[j]的定义相矛盾。所以s[l+1..1+m]≠t[1..m]。即对于所有的l：k+1≤l≤k+j-π[j]-1,s[l+1..l+m]不可能与t[1..m]完全匹配。
(ⅱ)当l=k+j－π[j]时，由于已得到的部分匹配有s[l+1..i]=s[k+j-π[j]+1..i]=t[j-π[j]+1..j],又因为t[1..π[j]]是t[1..j]的真后缀，即t[1..π[j]]= t[j－π[j]+1..j],s[l +1..i] = t[1..π[j]],即s[l+1..l+m]与t[1..m]已有长为π[j]的部分匹配。如图3.2.1所示。
按(ⅰ)和(ⅱ)的分析，我们可以得出结论：如果我们在主串s的k处得到s[k+1..k+m]与t[1..m]的部分匹配s[k+1..i]=t[1..j]，m＞j≥1，那么s中接着可能与t[1..m]完全匹配的子串是s[l+1..l+m]，其中l =k+j-π[j]=i-π[j]，而且s[l+1..l+m]与t[1..m]已有部分匹配s[l+1..i]=t[1..π[j]]。因此，接着要检测的是s[i+1]与t[π[j]+1]是否相等，即继续朝前匹配，不必回头。显然这将大大地提高找模式匹配的效率（见后面的复杂性分析）。
这就是D.E.Knuth，J.H.Morris和 V.R.Pratt 提出的对朴素的模式匹配算法加以改进的算法。因此人们称之为KMP算法。
2．KMP算法的流程图。
入口
Compute-Prefix-function(t,pi)
s.length=>n,t.length=>m
0=>j,1=>i
j>0且s[i]≠t[j+1] Yes π[j]=>j
No
s[i]=t[j+1] No
Yes
j+1=>j
j=m No
Yes
i+1=>i 输出k=i-m
π[j]=>j
No i=n
Yes
出口
图3.2.2
其中Compute-Prefix-function(t,pi)求T[1..m]的前缀函数π[1..m].
3．KMP算法用Pascal语言描述。
我们用Pascal的一个过程来表达KMP算法，过程取名为KMP_Matcher:
Proc. KMP_Matcher (var s,t:string)；
var m，n，i，j:integer；
Pi:array[1..t.length] of integer；
begin
(1) Compute_Prefix_function（t,pi）；
(2) n:=s.length；
(3) m:=t.length；
(4) j:=0；
(5) for i:=1 to n do
begin
(6) while j>0 and s.chs [i]<>t.chs[j+1]do j:=Pi[j]；
(7) if s.chs[i]=t.chs[j+1] then
begin
(8) j:=j+1；
(9) if j=m then begin print (i-m)；
j:=Pi[j]
end
end
end
end；
4．KMP算法的复杂性分析：
很明显，KMP算法的空间复杂性S（m,n）=θ（m+n）。
关于KMP的时间复杂性,首先根据求前缀函数Compute-Prefix-function的时间复杂性分析的结果，语句（1）需要θ(m)，而语句（2），（3），（4）显然各只要θ(1)的时间。语句（7）也只需θ(1)的时间，它在n次的for循环体中共需θ（n）的时间。语句（6）的while循环体，也只需θ（1）时间，循环次数与j有关，是个隐含值。与Compute-Prefix-function的分析类似，嵌套的语句（5）、（6），只需θ（n）的时间。因此，在最坏情况下，KMP_Match累计只需θ（m+n）的时间。
5．结论
KMP算法对朴素算法的改进是明显的，因为前者只需要θ（m+n），但后者却需要θ（mn）。KMP算法能对朴素算法作出改进的关键在于前者看到后者没有充分地利用匹配过程中所得到的每一个部分匹配，并找到充分利用它们的窍门。
无双注释:
KMP算法的基本就是当出现不匹配时, 把s的指针向右移动尽可能远
朴素算法则是直接回溯,只是向右移1,然后从头开始匹配
KMP则是向右移尽可能多, 并且下一步不一定从模式起始处开始匹配
看下面的next[i]求值方法可以理解下一步的偏移量
要理解KMP 先要理解next数组的意义
next数组是根据模式串T生成的 表示模式串T中前面重复数组的长度
下面是具体生成next数组的例子, next数组的第一个元素不用,一般设置为-1,第二个元素开始是匹配部分的值
模式: gagaagagga
开始:模式与复制 next[i]
0 -1 不需要,注意只有这个是-1
1 g 0 没有从开始就匹配的串,这个值都是0
g
2 ga 0 没有从开始就匹配的串
ga
3 gag 1 从开始匹配的串的长度是1
gag
4 gaga 2 匹配部分长度是2
gaga
5 gagaa 0 匹配部分的长度是0
gagaa
6 gagaag 1 匹配部分长度是1
gagaag
7 gagaaga 2 匹配部分长度是2
gagaaga
7 gagaagag 3 匹配部分长度是3
gagaaga
7 gagaagagg 1 匹配部分长度是1
gagaaga
7 gagaagagga 2 匹配部分长度是2
gagaaga
所以next数组的值是
NEXT[i]下标: 0 1 2 3 4 5 6 7 8 9 10
值 -1 0 0 1 2 0 1 2 3 1 2
算法的C代码
void Compute_Prefix_function(vector<int>& next,const char* t)
{
int t_len = strlen(t);
next.swap(vector<int>(t_len+1,0)); // 调整next数组,因为next数组从第二个元素开始使用, 长度为strlen(t)+1
next[0] = -1;
next[1] = 0;
int val = 0; // 用来设置t+1的值,保存上一次匹配从开始处的几个字符
for( int i = 1;i<t_len; i++ ){
// 查看从当前串与开始处的匹配程度,
// 但是我们并不用每次都从头开始,(如果你觉得不可理解, 可以根据上例从头开始计算next数组)
// 假如上一次已经匹配了val次,并且上次指针指到t[i]
// 那我们这次只需要检查t[i+1] == t[val+1]就可以,
// 如果t[i+1] != t[val+1],那退一步, 看看 它是不是等于 t[next[val+1]],next[val+1]表示它前面匹配的首部长度
// 如果还是不等,那再递减,这样只是为了加快性能
while( val > 0 && t[i] != t[val] )
val = next[val];
if( t[val] == t[i] ){
val ++;
next[i+1] = val;
}
else
next[i+1] = 0; // 重置从开始处的匹配长度
}
}
//
// 算法原理: 当发现不匹配时, 不进行回溯,而是向前进行尽可能多
//
static void KMP_Matcher(const char* s,const char* t)
{
vector<int> next;
Compute_Prefix_function(next,t);
int s_len = strlen(s);
int t_len = strlen(t);
int next_idx=0;
for( int i =0; i< s_len; i++ ){
// 如果在某处没有匹配(s[i]与t[next_idx]),
// 那对pattern T向前回溯,
// 看看有没有跟pattern的前一小部分匹配的
// 一直回溯到没有任何匹配才继续下一步
while( next_idx>0 && s[i] != t[next_idx] )
next_idx = next[next_idx];
// 如果有匹配,那pattern string 指针向前一步,
// 如果没有匹配, 也不需要对 src string回溯,
// 因为src string在这之前里面是没有与 pattern str 开始处匹配的
// 如下:
// KMP_Matcher("gcatcgcagagagtatacagtacg","gcagagag")
// 1 gcat
// gca
// 这时不需要再回到cat来匹配gca,因为它是不匹配的
if( s[i] == t[next_idx] )
next_idx ++;
if( next_idx == t_len )
printf("KMP_Matcher:\tS[%s]\tT[%s] pos[%d]\n",s,t,i - t_len+1);
}
}