关于java:KMP字符串匹配算法

KMP 算法是一种改良的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因而人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的外围是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到疾速匹配的目标。

请问，在字符串 T 中是否蕴含 P 的 “ababc”?

咱们能够从第一个字符开始比对，如下图：

在第四次比对的时候，咱们发现 T 字符串和 P 字符串并不统一。
咱们将字符串 P 整体后移一位从新进行比照。

第一次比对咱们就发现 T 字符串和 P 字符串比对不上。所以咱们须要持续后移 P 字符串进行比照。

以此类推，当所有字符能匹配上则阐明匹配胜利，如果匹配到 T 的开端都没有胜利的话则失败，此算法效率很低。

请问，在字符串 T 中是否蕴含 P 的 “ababc”?

第一步：
在学习 KMP 算法之前，咱们须要先理解前缀表 (Prefix Table)。

咱们先做的就是找到字符串长度较短的字符串，也就是字符串 P。

a b

a b a

a b a b

一共有四个前缀。

第二步：

咱们须要找出最长公共前后缀并且比原始字符串短。

这句话有点不太好了解，咱们应用 a b a b 来举例子。

咱们能够看到 a b a b 最长前缀就是 a b a，最长后缀就是 b a b。

然而咱们发现这两个字符串显著是不一样的。

3 个字符的前后缀显著不同，所以咱们应用 2 个字符前后缀进行匹配看看。

咱们发现前缀是 a b 后缀也是 a b。这样咱们就晓得最长公共前后缀是 2。

而后咱们持续往上看 a b a 很显著它的公共前后缀就是 1。如果咱们用 2 来看的话就是 ab 和 ba 很显著是不同的。

ok。再往上就是 a b 很显著，1 是不匹配的。所以最长公共前后缀是 0。a 也一样。

咱们看下最终是怎么的。

咱们进行整体向右挪动一位，而后初始值赋为 -1 能够失去如下后果：

a	b	a	b	a
-1	0	0	1	2

这样咱们去进行和 T 字符串进行比对，当比对到下标为 3 时，咱们发现 a 和 b 不同匹配失败。

这个时候咱们应该怎么做？

咱们发现在 P 数组中下标为 3 的 b 匹配谬误，而 b 的前缀表是 1，咱们须要将 P 数组下标为 1 的地位挪动 T 数组匹配失败的地位。

然而咱们发现匹配还是谬误的，咱们能够晓得 b 的前缀表是 0 所以咱们让下标为 0 的地位整体挪动到 T 数组匹配失败的地位。

咱们从新进行匹配，发现第一个 a 相等，第二个 b 和 c 不相等。

咱们继续移动，b 的前缀表是 0 所以咱们让下标为 0 的地位整体挪动到 T 数组匹配失败的地位。然而还是 a 和 c 匹配失败。

然而咱们晓得 a 的前缀表是 -1 也就是一个空的字符串，咱们将空的字符串对准匹配失败的地位， 等同于 - 1 就是整体右移一位

这个时候咱们持续进行匹配，发现曾经匹配胜利了！

举一个例子：

如果咱们使用暴力搜寻的话咱们会发现咱们须要将 P 字符串始终后移一位，须要四次后移才可匹配胜利。

如果咱们应用 KMP 来解决的话，还是首先咱们须要晓得前缀表是多少，如下图：

a	a	a	a	b
-1	0	1	2	3

而后咱们进行比对。

前缀表为 3 匹配失败，将数组下标为 3 挪动至此，持续进行比照。

须要留神的是，咱们不须要再重头开始比照，只须要从下标为 3 的地位开始匹配即可

前面其实就是大同小异，持续后移匹配即可。

总结

由此咱们能够晓得，暴力搜寻每次挪动后都要从第一位开始从新匹配，而咱们用 KMP 的话咱们不须要再重头开始比照能够省去大量工夫。

应用 Java 代码如何先失去前缀表。

    private static void buildPrefixTable(char[] pattern, int[] prefix) {
        // 比照指针下标
        int len = 0;
        // 第一位不须要进行比对因为必定是 0
        prefix[0] = 0;
        // 因为第一位不须要进行比对，咱们从 1 开始
        int i = 1;
        // 最初一位不须要比拟因为咱们须要的前缀表是比原始字符串短
        int length = prefix.length -1;
        while (i < length) {if (pattern[i] == pattern[len]) {
                // 匹配胜利，自增持续匹配下一位字符
                len++;
                prefix[i] = len;
                i++;
            } else {if (len > 0) {
                    // 取得前一位的前缀
                    len = prefix[len - 1];
                } else {
                    // 没有找到只能是 0，i++ 持续匹配下一位
                    prefix[i] = len;
                    i++;
                }
            }
        }

        // 整体后移一位，将第一位批改为 -1
        for (int j = prefix.length - 1; j > 0; j--) {prefix[j] = prefix[j - 1];
        }
        prefix[0] = -1;
    }

整体逻辑代码如下：

    public static void main(String[] args) {
        String T = "ABABABCABAABABABAB";
        String P = "ABABCABAA";
        char[] text = T.toCharArray();
        char[] pattern = P.toCharArray();
        kmpSearch(text, pattern);
    }

    private static void kmpSearch(char[] text, char[] pattern) {
        int m = text.length;
        int n = pattern.length;
        int[] prefix = new int[n];
        buildPrefixTable(pattern, prefix);
        // 字符串 text 的指针下标
        int i = 0;
        // 字符串 pattern 的指针下标
        int j = 0;
        while (i < m) {if (j == n - 1 && text[i] == pattern[j]) {System.out.println("找到了！开始下标为：" + (i - j));
                j = prefix[j];
                // 如果未比拟的 pattern 长度已超出 text 剩下的长度则提前结束
                if (n - j > m - i) {break;}
            }
            if (text[i] == pattern[j]) {
                // 雷同的话自增匹配下一位
                i++;
                j++;
            } else {
                // 不同的话就将前缀值当下标进行整体挪动
                j = prefix[j];
                if (j == -1) {
                    // 如果值为 - 1 则阐明须要整体后移一位进行匹配
                    i++;
                    j++;
                }
            }
        }
    }

    /**
     * 构建前缀表
     */
    private static void buildPrefixTable(char[] pattern, int[] prefix) {
        // 比照指针下标
        int len = 0;
        // 第一位不须要进行比对因为必定是 0
        prefix[0] = 0;
        // 因为第一位不须要进行比对，咱们从 1 开始
        int i = 1;
        // 最初一位不须要比拟因为咱们须要的前缀表是比原始字符串短
        int length = prefix.length -1;
        while (i < length) {if (pattern[i] == pattern[len]) {
                // 匹配胜利，自增持续匹配下一位字符
                len++;
                prefix[i] = len;
                i++;
            } else {if (len > 0) {
                    // 取得前一位的前缀
                    len = prefix[len - 1];
                } else {
                    // 没有找到只能是 0，i++ 持续匹配下一位
                    prefix[i] = len;
                    i++;
                }
            }
        }

        // 整体后移一位，将第一位批改为 -1
        for (int j = prefix.length - 1; j > 0; j--) {prefix[j] = prefix[j - 1];
        }
        prefix[0] = -1;

        System.out.println(Arrays.toString(prefix));
    }

输入后果：

[-1, 0, 0, 1, 2, 0, 1, 2, 3]
找到了！开始下标为：2

关于java:KMP字符串匹配算法

什么是 KMP 算法？

暴力搜索算法实现

KMP 算法实现

暴力搜寻和 KMP 区别

Java 代码实现 KMP 算法