KMP字符串匹配

假设我们有这样一个要求,一个字符串S,一个匹配字符串P,我们想知道匹配串P是否被包含在字符串S中,如果包含那它在S的什么位置上?

解决这个问题最简单的方法就是暴力匹配,匹配串中的一个元素匹配到了,就接着向后匹配,如果匹配失败,就整体后移一位,再重新匹配.

举个例子,按如下2个字符串要求我们看下匹配过程是怎么样的.

字符串S: DABABCABABCABDB

匹配串P: ABCABD

匹配过程,如表格所示:

可见匹配过程中,字符串S的指针会不仅会右移,还会左7移,如第3次匹配过程;

整体匹配次数大致是n*m,其中n和m分别是字符串S和匹配串P的长度,时间复杂度也就是O(n*m),那有没有更好的方式去完成匹配呢?

仔细观察匹配过程,我们发现第4行匹配过程中,当匹配到D时,虽然不匹配成功,但是我们是可以知道[D]元素前面的2个元素是[AB]和匹配串的前缀字符[AB]是匹配的,那我们之间比较第3个元素[C]就可以了,就可以减少2次比较运算和字符串S指针的回溯.

也就是说在某一元素匹配不成功后,直接判断下一指定索引元素就可以达到目的,那存储这一指定元素位置的索引,我们称之为next[] 数组.

按这样的思路D.E.Knuth，J.H.Morris和V.R.Pratt 三人一起提出了一种新的算法,也就是著名的KMP算法.KMP算法的主要思想是:

1. 字符串指针不回溯

2. 当不匹配时,匹配串尽量少回溯,确定向右最大滑行距离

为达到这样的效果,要怎么做呢?

这里有必要介绍两个概念:真前缀和真后缀

字符串: book

真前缀:b, bo, boo

真后缀:k, ok, ook

还有一个记录偏移量的数组next[]

1. i=0, 固定值为 -1

2. i=1, 索引i对应真前缀A, 最长相同真前缀和真后缀长度为 0

3. i=2, 索引i对应真前缀AB, 最长相同真前缀和真后缀长度为 0

4. i=3, 索引i对应真前缀ABC, 最长相同真前缀和真后缀长度为 0

5. i=4, 索引i对应真前缀ABCA, 最长相同真前缀和真后缀长度为 1

6. i=5, 索引i对应真前缀ABCAB, 最长相同真前缀和真后缀长度为 2

7. i=6, 这里表示匹配结尾,没有实际意义

那我们重新来看下使用了KMP算法的匹配过程

1. A与D匹配失败,A对应next[0]值为-1,匹配串P整体后移一位,重新与字符串S匹配.

2. C与A匹配失败,C对应next[2]值为0,匹配串P将索引位置0的元素[A]移到不匹配位置,其他元素也随之移动,重新开始匹配

3. D与A匹配失败,D对应next[5]值为2,匹配串P将索引位置2的元素[C]移到不匹配位置,其他元素也随之移动,重新开始匹配

4. C与A匹配失败,C对应next[2]值为0,匹配串P将索引位置0的元素[A]移到不匹配位置,其他元素也随之移动,重新开始匹配

5. 匹配成功

总结一下,通过辅助数组next[],确定整体匹配过程中,匹配串P的某个元素该与字符串S匹配,避免字符串S的指针回溯;

利用辅助数组next[],确定匹配失败时,后续匹配串该如何移动和重新比较,减少比较次数;

时间复杂度为O(n+m),其中n和m分别是字符串S和匹配串P的长度.

留个疑问,注意观察第4行匹配过程,看看这个next算法是否就是最合理的呢?我们下一节在来讲这个next算法的优化.

注意: 真前缀和前缀的区别,真后缀和后缀的区别,

真前缀是不包括自身的,真后缀也是同理;

还是以字符book为例,

真前缀: b ,bo, boo

前缀: b ,bo, boo, book

真后缀:k, ok, ook

后缀:k, ok, ook, book

next方法:

    private static int[] getNext(char[] p) {
        int[] next = new int[p.length];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < p.length - 1) {
            //p[k]表示前缀，p[j]表示后缀
            if (k == -1 || p[j] == p[k]) {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
            System.out.println("in-next:" + Arrays.toString(next));
        }
        return next;
    }

kmpSearch方法:

 private static int kmpSearch(String source, String target) {
        int i = 0;
        int j = 0;
        int sLen = source.length();
        int pLen = target.length();
        char[] s = source.toCharArray();
        char[] p = target.toCharArray();
        int[] next = getNext(source.toCharArray());
        while (i < sLen && j < pLen) {
            //如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
            if (j == -1 || s[i] == p[j]) {
                i++;
                j++;
            } else {
                //如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                //next[j]即为j所对应的next值
                j = next[j];
            }
        }
        if (j == pLen) {
            return i - j;
        } else {
            return -1;
        }
    }

main方法:

   public static void main(String args[]) {
        String str = "DABABCABABCABDB";
        System.out.println(Arrays.toString(getNext("ABCABD".toCharArray())));
        System.out.println(kmSearch(str, "ABCABD"));
    }