共计 3338 个字符，预计需要花费 9 分钟才能阅读完成。
这篇文章主要是介绍 KMP 模式匹配算法，在正式介绍 KMP 之前我们先看一下普通模式匹配，由普通模式匹配在进一步的推导 KMP 模式会更容易理解。
字符串的普通模式匹配
普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。
public int match(String S,String T){
int i = 0;
int j = 0;
while(i < S.length() && j < T.length()){
if(S.charAt(i) == T.charAt(j)){
i++;
j++;
}else{
i = i – j + 1;
j = 0;
}
}
if(j >= T.length()){
return i – T.length();
}else{
return 0;
}
}
普通模式匹配的时间复杂度最坏的情况（即 T 在 S 的末尾）为 O（(m-n+1)*n）。这种算法的优点是实现简单，缺点也显而易见那就是效率较低。jdk String 类内的静态方法 indexOf 底层使用的就是类似该种算法。
KMP 模式匹配算法推导
回溯推导
为了方便理解 KMP 模式，我们先看一下普通模式模式的流程：
栗子 1：
主串：S = “abcdefgab”
子串：T = “abcdex”
观察下普通模式匹配算法，对于要匹配的子串 T =“abcdex”来说
首字母 ”a” 与后面的串 ”bcdex” 中的任意一个字符都不相等;
串 ”bcde” 与主串 S 的第 2 - 5 位相等，那么首字母 ”a” 就不可能与主串 S 的第 2 - 5 位相等。
所以，第 2 3 4 5 的判断都是不需要的，这是个理解 KMP 模式的关键。
那么问题来了，如果 T 串后面还含有首字母 ”a” 的字符会怎么样呢？我们在看一个例子：
粟子 2：
主串：S = “abcabcabc”
子串：T =“abcabx”
对于要比配的子串 T = “abcabx” 来说，
T 的首字母 ”a” 与 T 的第 2 个字符 ”b”、第 3 个字符 ”c” 均不等，且 T 的第 1 - 3 位字符与主串 S 的第 1 - 3 相等，所以，步骤 2 和步骤 3 可以省略；
T 的前 2 位串 ”ab” 与 T 的第 4 - 5 串 ”ab” 相等，且 T 的第 4 - 5 串 ”ab” 与主串 S 的第 4 - 5 串 ”ab” 相等，得出 T 的前 2 位串与 S 的第 4 - 5 也相等，可以省略。
最后，第 6 步的前两次比较也是不需要的，直接比较 主串 S 的第 6 位的 ”a” 和子串 T 的第 3 位 ”c” 即可，如下图：
对比这两个例子，可以发现普通模式主串 S 的游标每次都是回溯到 i ++ 的位置。而经过上面的分析后发现，这种回溯方式其实是不需要的，KMP 模式就是解决了这些没有必要的回溯。
既然要避免 i 的回溯，那么我们就要在子串 T 的游标 j 上下工夫了。通过观察也可发现，如果 T 的首字母与自身后面的字符有相等的情况，那 j 值的变化就会不相同。
例子 1 内 j 的变化，由于首字母 ”a” 与后面的字符都不相等，则 j 由 6 变回了 1。
例子 2 内 j 的变化，由于前缀 ”ab” 与后面的 ”ab” 相等，因此 j 从 6 变回了 3。
有没有看出什么规律？提示一下：
例子 1 内与前缀相同的字符个数为 0，j 变成了 1。
例子 2 内与前缀相同的字符个数为 2，j 变成了 3。
j 的变化取决也当前字符之前的串的前后缀的相似度。
回溯公式
根据上一节的推导，我们可以将 T 串各个位置的 j 的变化定义为一个数组 next，next 的长度就是 T 串的长度，我们可以得到下面的函数定义（为了后面读程序方便理解，所以该函数是遵循数组下标从 0 开始的规范）：
我们来手工验证一下该函数。
T = “abcdex”
j
123456
模式串 T
abcdex
next[j]
000000
if j = 0, next[0] = 0;
if j = 1, ‘p~0~ … p~k~’ = ‘p~j-k~ … p~j~’ –> ‘a’ <> ‘b’ ,next[1] = 0;
if j = 2, 子串 ”abc”，也没有重复的字符子串，next[2] = 0;
以后同理，所以最终 T 串的 ntxt[j] 为 000000。
例子就列举到这里，现在放下 KMP 的 Java 实现，其它实例大家可以使用程序进行验证。
KMP 模式匹配算法实现
public void getNext(String T,Integer[] next){
next[0] = 0; // 当 j = 0 时，next[0] = 0
int i = 1;
int j = 0;
int k = 0;
while (i < T.length() && j < i){
if(T.substring(0,j).equals(T.substring(i-j,i))){
k = j; // 若有相同子串，则记录下对应在 T 串内的位置，最终得出最长匹配成功的位置
}
j++;
if(j >= i){
next[i] = k; // 若一直未匹配成功，将 k = 0 赋值给 next[i]
j = 1;
k = 0;
i++;
}
}
}
我们来测试 几个字符串：
input: abcdex
output:000000
input: abcabx
output:000012
input: aaaaaaaab
output:001234567
下面是完整的 KMP 模式匹配算法的代码：
package string;
public class KMPMatch {
public void getNext(String T,Integer[] next){
next[0] = 0; // 当 j = 0 时，next[0] = 0
int i = 1;
int j = 0;
int k = 0;
while (i < T.length() && j < i){
if(T.substring(0,j).equals(T.substring(i-j,i))){
k = j; // 若有相同子串，则记录下对应在 T 串内的位置，最终得出最长匹配成功的位置
}
j++;
if(j >= i){
next[i] = k; // 若一直未匹配成功，将 k = 0 赋值给 next[i]
j = 1;
k = 0;
i++;
}
}
}
public int match(String S,String T){
int i = 0;
int j = 0;
Integer[] next = new Integer[T.length()];
getNext(T,next);
while(i < S.length() && j < T.length()){
if(j == 0 || S.charAt(i) == T.charAt(j)){
i++;
j++;
}else{
j = next[j];
}
}
if(j >= T.length()){
return i – T.length();
}else{
return 0;
}
}
public static void main(String[] args) {
String S = “aaaabcde”;
String T = “abcd”;
System.out.println(new KMPMatch().match(S,T));
}
}
对于方法 getNext 来说，若 T 的长度为 m，因只涉及简单的单循环，其时间复杂度为 O(m)，由于 i 不进行回溯，while 循环的时间复杂度为 O(n)。因此，整个算法的时间复杂度为 O(m+n)。
对于 KMP 模式来说，仅当子串与主串之前存在许多“部分匹配”的时候才体现出它的优势，否则两者差异并不明显。
KMP 模式匹配算法的优化
看下面这个例子：
S = “aaaabcde”
T = “aaaaax”
T 的 next 分别为 001234，两个串的匹配流程如下：
从流程中可发现，当中的步骤 2 3 4 5 都是多余的判断。由于 T 串的第 2 3 4 5 位置的字符都与首字符相等，那么就可以用首位 next[0] 值去取代与它相等的字符的 next[j]，下面就是对 getNext 方法进行的改良，代码如下：
public void getNextVal(String T,Integer[] nextVal){
nextVal[0] = 0; // 当 j = 0 时，next[0] = 0
int i = 1;
int j = 0;
int k = 0;
while (i < T.length() && j < i){
if(T.substring(0,j).equals(T.substring(i-j,i))){
k = j; // 若有相同子串，则记录下对应在 T 串内的位置，最终得出最长匹配成功的位置
}
j++;
if(j >= i){
// 当前字符与前缀字符相同中，则当前字符 j 为 nextVal[i]
if(T.charAt(i) == T.charAt(k)){
nextVal[i] = nextVal[k];
}else {
nextVal[i] = k;
}
j = 1;
k = 0;
i++;
}
}
}
学习是一个过程，对学习到的知识进行理解、吸收、整理，并将其按自己的理解进行输出。
参考材料：《大话数据结构》
