??? ??? 設有主串s和子串t，子串t定位是指在主串s中找到一個與子串t相等的子串。通常把主串s稱為目標串，把子串t稱為模式串，因此定位也稱作模式匹配。模式匹配成功是指在目標串s中找到一個模式串t。
??? ??? 傳統的字符串模式匹配算法（也就是BF算法）就是對于主串和模式串雙雙自左向右，一個一個字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。
??? ??? KMP
算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡稱KMP算法。KMP算法是字符串模式匹配中的經典算法。和BF算法相比，KMP算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結果使得算法時間復雜度只為O（n＋m）。下面說說KMP算法的原理。
假設我們有個模式串為“abdabcde”存于數組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]（稱為失效函數）的公式如下：
next[i]
=
(
上面的公式中非t字母和數字組成的為數組下標)
??? ??? 應該如何理解next數組呢？在匹配過程中，如果出現不匹配的情況（當前模式串不匹配字符假定為t[i]），它所對應的next[i]的數值為接下來要匹配的模式串的字符的索引；也就是說，出現不匹配的情況時，模式串的索引指針要回溯到中next[i]所對應的位置，而主串的索引指針保持不變。
??? ??? 特別的，next數組中的next[0]和next[1]的取值是固定的，為了標識出首字母，需要假定next[0]為－1（取為－1是考慮到C語言中的數組索引以0開始）。在實現的時候，要實現公式中情況的處理需要些技巧，下面給出具體的實現：
#
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”，如果按照上面的做法，這時模式串只會回溯一個索引，由于仍不匹配，模式串還會回溯一個索引，直到索引位置到了首字符，主串的索引指針才會前進一位，這樣就會浪費一些不必要的比較時間。出現這種情況的原因是模式串中位置i的字符與next[i]對應的字符相同，需要修正next[i]為next[i]對應的字符的索引。下面列出“aaaadd”修正的nextval數組的內容：
|
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
|
??? ??? 修正函數如下：
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];
????????}
????}
}
??? ??? 注：以上函數在gcc4.1下編譯運行通過，使用C而不是java的原因主要希望借此熟悉一下學過的語言。以上內容絕大部分為《數據結構習題與解析》一書中的相關內容，我只是費勁將其敲打出來。實話實說，我覺得自己并沒有寫明白這個算法，如果給出一個具體的匹配過程會更好，但寫起來就要麻煩許多。對未讀懂此文的朋友表示歉意。