KMP 算法

KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的，KMP 算法的时间复杂度 O (m+n)。

相同前后缀

KMP 算法之所以能够快速匹配，主要是因为在迭代过程中并不是逐个查找，而是根据模式串的最长相同前后缀表进行跳跃查找。这里的相同前后缀指的是字符串中前缀和后缀相同的子串，不包括整个字符串。

示例 1：“aba”，“a” 既是 “aba” 的前缀，也是 “aba” 的后缀，所以 “a” 就是 “aba” 的相同前后缀。
示例 2：“ababa”，“a” 是 “ababa” 的相同前后缀，“aba” 也是 “ababa” 的相同前后缀。

下面演示 “abacabad” 的最长相同前后缀表是如何得到的。

查找演示

看看 KMP 算法如何使用最长相同前后缀表进行查找。

字符串，“abacabaabacabad”
模式串，“abacabad”

匹配图解

字符串和模式串前 7 个字符都能匹配上，当 i=7，j=7 时，匹配失败。如果是暴力查找，那么就需要让 i=1，j=0，然后重新开始匹配，如下:

如果是 KMP 算法会是怎样呢？
直接将模式串已成功匹配的前缀 “aba” 和字符串已成功匹配的 “aba” 对齐，让 i=7，j=3，然后继续匹配。如下：

因为只有模式串成功匹配的子串 “abacaba” 中的某个前缀和字符串中已经匹配成功的子串 “abacaba” 中的某个后缀相同，后续的比较才有意义，而且只有取最长的相同前后缀才不会遗漏可能的匹配，而 “aba” 就是 “abacaba” 的最长相同前后缀。

i=7，j=3 匹配失败，所以继续将模式串已成功匹配的前缀 “a” 和字符串已成功匹配的 “a” 对齐，让 i=7，j=1，然后继续匹配。如下：

i=7，j=1 匹配失败，因为已成功匹配的子串没有相同前后缀，所以将模式串整体后移和字符串未匹配成功的字符对齐，让 i=7，j=0，然后继续匹配下去。如下：

最终匹配完成，从第一第二阶段来看，KMP 算法比暴力查找算法少了很多无用的循环，所以效率比较比暴力查找自然快多了。注：KMP 算法时间复杂度是 O (m+n)，暴力查找是 O (m*n)。

算法实现

1public int indexOf(String text, String pattern) {
2    if ("".equals(pattern)) {
3        return 0;
4    }
5    int[] table = new int[pattern.length()];
6    int i = 0, j = 1;
7    while (j < table.length) {
8        if (pattern.charAt(i) == pattern.charAt(j)) {
9            table[j++] = i + 1;
10            i++;
11        } else {
12            if (i == 0) {
13                j++;
14            } else {
15                i = table[i - 1];
16            }
17        }
18    }
19
20    i = 0;
21    j = 0;
22    while (i < text.length()) {
23        if (text.charAt(i) == pattern.charAt(j)) {
24            i++;
25            j++;
26        } else {
27            if (j == 0) {
28                i++;
29            } else {
30                j = table[j - 1];
31            }
32        }
33        if (j == pattern.length()) {
34            return i - j;
35        }
36    }
37    return -1;
38}