模式搜索算法KMP

为了说明算法细节，我们举一个实际例子来说明。假设W=“ABCDABD”，S=“ABC ABCDAB ABCDABCDABDE”。算法的状态在任意时刻都只由两个整数决定：

m表示S中可能匹配W的起始位置 i表示W中正在比较的字符下标 每一步中，我们比较S[m+i]和W[i]，如果相等则继续下一个字符。 1，从第一个字符开始匹配，因B与A不相等，故后移一位。 2，从第一个字符开始匹配，B与A不相等，再次后移。 3，直到有一个字符相同，继续往下比较，直到发现不同。 4，此时该后移多少？应该后移到如图位置。部分匹配值在后面说明。 移动位数 = 已匹配的字符数 - 对应的部分匹配值 根据相同原理，继续进行比较。 直到最后i一直匹配到W的最后一位，匹配成功。

6，下面介绍部分匹配值是如何计算的。 首先，有两个概念：“前缀”和“后缀”。有如下定义：前缀指除了最后一个字符以外，一个字符串的全部头部组合；“后缀”指除了第一个字符以外，一个字符串的全部尾部组合。 在此基础上，“部分匹配值”就是“前缀”和“后缀”中最长的公共元素的长度。以ABCDABD为例：

“A"的前缀和后缀都为空集，共有元素的长度为0； “AB"的前缀为[A]，后缀为[B]，共有元素的长度为0； “ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； “ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； “ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A”，长度为1； “ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB”，长度为2； “ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

“部分匹配”实质是字符串头部和尾部可能有重复的串，搜索移动的时候，我们能通过此规则跳过一定的字符，达到减小复杂度的目的。

KMP算法的效率

算法的两部分“计算部分匹配值”和“寻找匹配串”，复杂度分别为O(n)和O(k)，因此算法整体复杂度为O(n+k)。这项复杂度不因W和S中的重复模式数目而改变。

最后放上实现代码

public class KMP {
    // kmp算法实现，返回所有匹配处的下标
    static ArrayList<Integer> kmp_search(char[] target, char[] pattern) {
        if (target == null || pattern == null) {
            throw new IllegalArgumentException("null char array");// null param
        }
        if (target.length == 0 || pattern.length == 0
                || pattern.length > target.length) {
            throw new IllegalArgumentException("invalid parameter");// err return
        }
        int[] pmt = get_pmt(pattern);//获取部分匹配数组
        ArrayList<Integer> kmpResult = new ArrayList<Integer>();
        int S = target.length;// target 元素个数
        int W = pattern.length;// pattern 元素个数
        int delta;//表示patter该往后移动的位数
        int m;// m表示target中可能匹配W的起始位置
        int i;// i表示pattern中正在比较的字符下标
        for (m = 0; m < S - W + 1; m += delta) {
            delta = 1;
            for (i = 0; i < W; i++) {
                if (pattern[i] != target[m + i]) {
                    if (i != 0)
                        delta = (i - pmt[i - 1]);
                    break;
                }
            }
            if (i == W) {
                kmpResult.add(m);
            }
        }
        return kmpResult;
    }

    // 生成部分匹配表
    static int[] get_pmt(char[] pattern) {
        int len = pattern.length;
        int[] pmt = new int[len];
        int i, j, k, max_cc;
        for (i = 0; i < len; i++) {
            max_cc = 0;
            // prefix pattern[0...j]
            // postfix pattern[k...i]
            for (j = 0; j < i; j++) {
                for (k = 0; k <= j; k++) {
                    if (pattern[k] != pattern[i - j + k]) {
                        break;
                    }
                }
                if (k == j + 1)
                    max_cc = Math.max(max_cc, k);
            }
            pmt[i] = max_cc;
        }
        return pmt;
    }

    public static void main(String[] args) {
    // 测试
        char[] target = "AABAACAADAABAAABAA".toCharArray();
        char[] pattern = "ABAA".toCharArray();
        System.out.println(kmp_search(target, pattern));
    }
}