??? ??? 設(shè)有主串s和子串t，子串t定位是指在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標(biāo)串，把子串t稱為模式串，因此定位也稱作模式匹配。模式匹配成功是指在目標(biāo)串s中找到一個模式串t。
??? ??? 傳統(tǒng)的字符串模式匹配算法（也就是BF算法）就是對于主串和模式串雙雙自左向右，一個一個字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時間復(fù)雜度為O（n＊m），其中n和m分別為串s和串t的長度。
??? ??? KMP
算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡稱KMP算法。KMP算法是字符串模式匹配中的經(jīng)典算法。和BF算法相比，KMP算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結(jié)果使得算法時間復(fù)雜度只為O（n＋m）。下面說說KMP算法的原理。
假設(shè)我們有個模式串為“abdabcde”存于數(shù)組t，我們要求的就是模式串的next值，見下表所示：
|
i
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
t[i]
|
a
|
b
|
d
|
a
|
b
|
c
|
d
|
e
|
|
next[i]
|
-1
|
0
|
0
|
0
|
1
|
2
|
0
|
0
|
??? ??? 求模式t的next[i]（稱為失效函數(shù)）的公式如下：
next[i]
=
(
上面的公式中非t字母和數(shù)字組成的為數(shù)組下標(biāo))
??? ??? 應(yīng)該如何理解next數(shù)組呢？在匹配過程中，如果出現(xiàn)不匹配的情況（當(dāng)前模式串不匹配字符假定為t[i]），它所對應(yīng)的next[i]的數(shù)值為接下來要匹配的模式串的字符的索引；也就是說，出現(xiàn)不匹配的情況時，模式串的索引指針要回溯到中next[i]所對應(yīng)的位置，而主串的索引指針保持不變。
??? ??? 特別的，next數(shù)組中的next[0]和next[1]的取值是固定的，為了標(biāo)識出首字母，需要假定next[0]為－1（取為－1是考慮到C語言中的數(shù)組索引以0開始）。在實現(xiàn)的時候，要實現(xiàn)公式中情況的處理需要些技巧，下面給出具體的實現(xiàn)：
#
include?<stdio.h>
#include?<stdlib.h>
typedef?struct?QString?{
????char
*
?cs;
????
int
?len;
}String;
void?GetNext(String?s
,
int
?
next
[]){
????
int
?len?
=
?s
.
len;
????
int
?i?
=
?
0
;
????
int
?k?
=
?
-
1
;
????
next
[
0
]?
=
?
-
1
;
????
while
(i?
<
?len
-
1
){
????????
if
(k
==-
1
?
||
?s
.
cs[i]?
==
?s
.
cs[k]){
????????????i
++
;
????????????k
++
;
????????????
next
[i]?
=
?k;
????????}
else
{
????????????k?
=
?
next
[k];
????????}
????}
}
int
?KMPIndex(String?s
,
String?m){
????
int
?
next
[m
.
len]
,
i
=
0
,
j
=
0
;
????
int
?k;
????GetNext(m
,
next
);
???
while
(i
<
s
.
len??
&&
j
<
m
.
len){
????????
if
(j
==-
1
?
||
?s
.
cs[i]?
==
?m
.
cs[j]){
????????????i
++
;
????????????j
++
;
????????}
else
{
????????????j?
=
?
next
[j];
????????}
????}
????
if
(j?
>=
?m
.
len)
return
?i
-
m
.
len;
????
else
?
return
?
-
1
;
}
??? ??? KMP
算法也有需要改進的地方。對于模式串“aaaadd”在匹配時（假定被匹配串為“aaadddd”），可以看到，在匹配到索引3時，主串字符為“d”，模式串字符為“a”，如果按照上面的做法，這時模式串只會回溯一個索引，由于仍不匹配，模式串還會回溯一個索引，直到索引位置到了首字符，主串的索引指針才會前進一位，這樣就會浪費一些不必要的比較時間。出現(xiàn)這種情況的原因是模式串中位置i的字符與next[i]對應(yīng)的字符相同，需要修正next[i]為next[i]對應(yīng)的字符的索引。下面列出“aaaadd”修正的nextval數(shù)組的內(nèi)容：
|
i
|
0
|
1
|
2
|
3
|
4
|
5
|
|
t[i]
|
a
|
a
|
a
|
a
|
d
|
d
|
|
next[i]
|
-1
|
0
|
1
|
2
|
3
|
0
|
|
nextval[i]
|
-1
|
-1
|
-1
|
-1
|
0
|
0
|
??? ??? 修正函數(shù)如下：
void?GetNextval(String?s
,
int
?nextval[]){
????
int
?len?
=
?s
.
len
,
i?
=
?
0
,
k?
=
?
-
1
;
????nextval[
0
]?
=
?
-
1
;
????
while
(i?
<
?len
-
1
){
????????
if
(k
==-
1
?
||
?s
.
cs[i]?
==
?s
.
cs[k]){
????????????i
++
;
????????????k
++
;
????????????
if
(s
.
cs[i]?
!=
?s
.
cs[k]){
????????????????nextval[i]?
=
?k;
????????????}
else
???nextval[i]?
=
??nextval[k];????????????
????????}
else
{
????????????k?
=
?nextval[k];
????????}
????}
}
??? ??? 注：以上函數(shù)在gcc4.1下編譯運行通過，使用C而不是java的原因主要希望借此熟悉一下學(xué)過的語言。以上內(nèi)容絕大部分為《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》一書中的相關(guān)內(nèi)容，我只是費勁將其敲打出來。實話實說，我覺得自己并沒有寫明白這個算法，如果給出一個具體的匹配過程會更好，但寫起來就要麻煩許多。對未讀懂此文的朋友表示歉意。