设有主串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的原因主要希望借此熟悉一下学过的语言。以上内容绝大部分为《数据结构习题与解析》一书中的相关内容，我只是费劲将其敲打出来。实话实说，我觉得自己并没有写明白这个算法，如果给出一个具体的匹配过程会更好，但写起来就要麻烦许多。对未读懂此文的朋友表示歉意。