简介

KMP算法是由 D.E. Knuth、J.H.Morris和 V.R. Pratt提出的，可在一个主文本字符串 S内查找一个词 W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。这个算法是由高德纳和沃恩·普拉特在 1974年构思，同年詹姆斯 ·H·莫里斯也独立地设计出该算法，最终由三人于 1977年联合发表。该算法减少了 BF算法中i回溯所进行的无谓操作，极大地提高了字符串匹配算法的效率。

思路

假设有两个字符串，S为：ABABCACABABCAA，T为：ABABCAA；要判断 S是否含有 T, 如果有则返回第一次出现的位置，否则返回 -1。

1. 列出 T的所有子串；

2. 计算每个子串的部分匹配值；
   2.1. 若子串只有一个字符，则为0；
   2.2. 否则，计算以第一个字符开始的子串与以最后一个字符结尾的子串最多能相等的位数；

   

3. 经过以上步骤后，得到以下对应关系：

   

4. 正式开始匹配，从 S[0]处开始，依次比较 S[i]与 T[i]，发现 T[6]≠S[6]；记录此时S的索引为j,T的索引为k

   

5. 此时，若是按暴力匹配的思路，会从 S[1]处重新开始，依次比较 S[i+1]与 T[i]，如下图所示：

6. 而KMP算法的思路是：
   6.1. 先斜位查 P[k-1]，得到1

6.2. 然后用 T[1]与 S[j]比较，这样可以跳过一些不必要的比较，提高效率

代码

    /**
     * KMP算法
     *
     * @param source
     * @param target
     * @return
     */
    public static int kmp(String source, String target) {
        // 部分匹配表
        int[] table = partialMatchTable(target);
        for (int i = 0, j = 0; i < source.length(); i++) {
            while (j > 0 && source.charAt(i) != target.charAt(j)) {
                j = table[j - 1];
            }
            if (source.charAt(i) == target.charAt(j)) {
                j++;
            }
            if (j == table.length) {
                return i - j + 1;
            }
        }
        return -1;
    }

    /**
     * 部分匹配表
     *
     * @param target
     * @return
     */
    private static int[] partialMatchTable(String target) {
        int[] table = new int[target.length()];
        table[0] = 0;
        for (int i = 1, j = 0; i < target.length(); i++) {
            while (j > 0 && target.charAt(i) != target.charAt(j)) {
                j = table[j - 1];
            }
            if (target.charAt(i) == target.charAt(j)) {
                j++;
            }
            table[i] = j;
        }
        return table;
    }

测试

    public static void main(String[] args) {
        String s = "ABABCACABABCAA";
        String t = "ABABCAA";
        System.out.printf("索引：%d", kmp(s, t));
    }

输出结果：

索引：7