KMP算法理解与Java实现

发表于 | 分类于

字符串匹配的KMP算法 — 阮一峰
明白KMP算法的原理后我们思考如何求出给定字符串的部分匹配值数组next，我们当然不可能每次都把所有前后缀写出来，那么我们要思考的就是如果我知道next[0]~next[i-1]的值，能不能求出next[i]? 答案是肯定的。

我们以字符串ACCCBAAACCCBAAC为例，依次求出next[i]的值：

Java代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int[] getNext(String s) {
        int len = s.length();
        int[] next = new int[len];
        char[] p = s.toCharArray();
        next[0] = 0;
        int k = 0;
        int i = 1;
        while (i < len) {
            while (k > 0 && p[k] != p[i]) {
                k = next[k-1];
            }
            if (p[k] == p[i]) {
                k++;
            }
            next[i] = k;
            i++;
        }
        return next;
    }

来看一道leetcode1392题，运用KMP算法可以简单的解决，我们只需要对上面的代码做简单的修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String longestPrefix(String s) {
        int len = s.length();
        int[] next = new int[len];
        char[] p = s.toCharArray();
        next[0] = 0;
        int k = 0;
        int j = 1;
        while (j < len) {
            while (k > 0 && p[k] != p[j]) {
                k = next[k-1];
            }
            if (p[k] == p[j]) {
                k++;
            }
            next[j] = k;
            j++;
        }
        return s.substring(0,k);
    }

OK，那么既然next数组已经求出来了，我们就可以回到我们最初的命题：举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//返回第一次匹配的索引
public static int longestPrefix(String s,String pattern) {
        char[] p = pattern.toCharArray();
        int[] next = getNext(pattern);
        int i = 0;
        int j = 0;
        while (i < s.length()) {
            while (j < p.length && i < s.length() && s.charAt(i) == p[j]) {
                if (j == p.length - 1) {
                    return i - j;
                }
                j++;
                i++;
            }
            if (j > 1) {
                j = j - next[j - 1];
            }
            i++;
        }
        return -1; //不匹配
    }