图解 KMP 算法

2020-01-10 11:41:34

前言

KMP（Knuth Morris Pratt）算法的核心思想是让模式串中的字符挨个和主串中的进行比对，直到找到了一个他们不一致的的字符，这个字符就记作坏字符，前面已经匹配成的记作好前缀，然后从中寻找某种规律尽可能的向后多移动几位数字来完成高效匹配

在传统的 BF 比对方式中可能就是将模式串依次向后移动一位然后挨个比较，这样效率比较低。

KMP 旨在寻找某种规律将模式串尽可能多的向后移动几位来提高匹配的效率

next 数组

通过这种好前缀匹配的方式，我们发现如果出现了字符不匹配的情况，前缀肯定是一致的，如果前缀不一致那么就将模式串向后移动

如果没有匹配到一个好前缀这模式串向后移动一位继续判断

知道了如上的哪一种情况后，我们继续还是拿这幅图进行匹配

我们肉眼观察可以发现可以将好前缀移动 4 位然后再进行比对是一种比较高效的做法

那么这移动的位数有什么数学规律呢？

作者将这种规律总结出了 next 数组也叫作失效函数（failure function），它是根据模式串来进行构建的与主串无关，构建过程如下

模式串值为：ababac

取出模式串的所有的前缀子串
从前缀子串中寻找可以匹配到的长的后缀子串
以前缀子串结尾的下标作为 next 数组的索引位置
以匹配到的长的后缀子串对应着前缀子串的位置作为 next 数组的值

这里说明下 next 数组的计算过程，以 aba 和 abab 为例。

aba 它的长度为 3 所以下标为 2（从 0 开始计数）。它的前缀有 a、ab 它的后缀有 a 和 ba，可以看到与前缀匹配的长后缀子串为 a 它的下标为 2，但是需要的是它对应的前缀子串的下标即 0，终得到 next[2] = 0

abab 它的长度为 4 所以下标为 3（从 0 开始计数）。它的前缀有 a、ab、aba 后缀有 b、ab、bab，此时与前缀匹配长的后缀子串为 ab 下标为 3（末尾字符）但是需要的是它对应的前缀子串也就是下标为 1 的位置，所以 next[3] = 1

next 数组可以说是实现 KMP 算法的核心，理解了他后面的就简单了，然后我们来看如何根据 next 数组来进行模式字符串匹配，还是如下图

此时主串中坏字符位置 i = 5 对应模式串中位置 j = 5，此时我们向前取一位 next 数组 next[j - 1] 也就是 j = next[4] + 1 = 2，然后发现 text[5] == partten[2]，那么我们可以 ++j 后继续进行比对

我们之前所说的移动模式串向后比对，在程序上其实就是将主串的坐标 i 和模式串的坐标 j 对应的字符进行比对，比如此处判断主串字符 text[5] == partten[3] 发现二者相等，那么 i 和 j 分别向后移动一位继续判断是否相等，发现 text[6] == partten[4] 相等，然后 i 和 j 再次向后移动一位发现 text[7] 为 b，partten[5] 为 c 他们不相等了。

此时发现了主串 i = 7 和模式串 j = 5 的时候他们不相等了，然后我们再次从 j = next[j - 1] + 1 == 3，发现 text[7] == partten[3] == b，那么 i 和 j 在向后移动一位，发现 text[8] != partten[4]

此时发现 i = 8，j = 4 的时候不匹配了，那么我们从 j = next[j - 1] + 1 = 2 发现 partten[2] != text[8]，这个时候就不能将 j 后移了，我们要再从 next 数组中查找 j = next[j - 1] + 1 == 0 发现没有找到了，这个时候 j 为 0 也就是从模式起始位置开始继续查找，发现 text[8] != partten[0] 那么 i 继续后移一位为 9 后发现 text[9] == partten[0] 然后 i 和 j 依次加 1 继续判断 text[10] == partten[1]...到达 j = 5 的时候发现 text[5] == partten[14] 匹配成功

后面几个匹配判断一样后成找到匹配一直的字符串

算法实现

public static int search(char[] text, char[] partten) {
        int parttenLength = partten.length;
        int[] next = getNexts(partten, parttenLength);
        int j = ;
        for (int i = ; i < text.length; i++) {
            while (j >  && text[i] != partten[j]) {
                j = next[j - 1] + 1;
            }
            if (text[i] == partten[j]) {
                ++j;
            }
            if (j == parttenLength) {
                return i - parttenLength + 1;
            }
        }
        return -1;
    }
    
    private static int[] getNexts(char[] partten, int m) {
        int[] next = new int[m];
        for (int i = ; i < m; i++) {
            next[i] = -1;
        }
        int k = -1;
        for (int i = 1; i < m; i++) {
            while (k != -1 && partten[k + 1] != partten[i]) {
                k = next[k];
            }
            if (partten[k + 1] == partten[i]) {
                ++k;
            }
            next[i] = k;
        }
        return next;
    }