java 实现KMP算法

Java实现KMP算法完整攻略

什么是KMP算法

KMP算法全称是Knuth-Morris-Pratt算法，是一个字符串查找算法，用于在一个字符串S中查找一个模式串P出现的位置。

KMP算法思想

KMP算法的思想是通过一个”部分匹配”的概念，当部分匹配发生后，可以知道一部分字符是匹配的，从而充分利用这个已知信息，避免从头再去比较已经比较过的字符。

KMP算法流程

KMP算法分为两个步骤：第一步是预处理，第二步是匹配。

第一步：预处理

预处理目的是得到一个数组next，用于在匹配时根据已经匹配的字符来确定下一步移动的位置。该数组的计算方式如下：

void getNext(int[] next, String pattern) {
    int j = 0;
    int k = -1;
    next[0] = -1;
    while (j < pattern.length() - 1) {
        if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

上述代码中，j表示匹配串的下标，k表示前缀串的下标。在计算next数组时，从第1个位置开始比较，k初始化为-1，表示前缀串不存在。如果当前j和k位置的字符匹配，则j和k都加1，同时将next[j]设置为k，表示在j位置匹配失败后，应该跳到k位置重新尝试匹配。如果当前字符不匹配，则将k更新为next[k]，继续尝试匹配。直到j到达字符串的长度减一处为止。

第二步：匹配

匹配时，通过已经预处理得到的next数组，来决定下一步移动的位置。匹配过程中，让j指向匹配字符串的第i个位置，k指向模式串的第0个位置，此时开始对j和k所指的字符串进行匹配。

int kmp(String s, String pattern) {
    int i = 0;
    int j = 0;
    int[] next = new int[pattern.length()];
    getNext(next, pattern);
    while (i < s.length() && j < pattern.length()) {
        if (j == -1 || s.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == pattern.length()) {
        return i - j;
    } else {
        return -1;
    }
}

上述代码中，i表示s的下标，j表示pattern的下标。如果当前s[i]和pattern[j]匹配，则i和j都加1。如果不匹配，则将j跳到next[j]的位置重新尝试匹配。如果j达到pattern的长度，则说明匹配成功，返回i-j的值。

示例

下面是两个示例，用来说明KMP算法的使用场景。

示例一

我们有两个字符串s和p：

s: ababababc
p: ababc

我们要在s中查找p是否出现。这时可以使用KMP算法。

预处理得到的next数组为：

p: a b a b c
i: -1 0 0 1 2
next: -1 0 0 1 2

下面是使用KMP算法查找p在s中出现的代码：

String s = "ababababc";
String p = "ababc";
int index = kmp(s, p);
if (index != -1) {
    System.out.println("p在s中从" + index + "开始出现");
} else {
    System.out.println("p不在s中出现");
}

运行代码后，可以得到输出结果：

p在s中从2开始出现

示例二

我们有一个字符串s，想要在中间进行插入，使其成为一个回文字符串。插入的字符可以是任意字符。

s: abca

如果使用暴力算法，需要将所有的插入情况都试一遍，时间复杂度为O(n^2)。而如果使用KMP算法，可以在预处理时将s倒序，然后将s和s的逆序拼接成一个新的字符串，这样就可以得到最大前缀回文子串和最大后缀回文子串。

预处理得到的next数组为：

s: a b c a
i: 0 1 2 3
next: 0 0 0 1

逆序得到的next数组为：

s: a c b a
i: 0 1 2 3
next: 0 1 0 0

拼接得到的next数组为：

s: a b c a a c b a
i: 0 1 2 3 4 5 6 7
next: 0 0 0 1 0 1 0 0

可以看到，拼接得到的next数组中，最后一个位置的值就是最大前缀回文子串和最大后缀回文子串的长度。

下面是使用KMP算法插入回文字符串的代码：

String s = "abca";
int[] next = new int[s.length()];
getNext(next, s);
int len = next[s.length() - 1];
StringBuilder sb = new StringBuilder(s);
for (int i = 0; i < len; i++) {
    sb.append(s.charAt(len - i - 1));
}
System.out.println(sb.toString());

运行代码后，可以得到输出结果：

abcacba

总结

本文详细讲解了KMP算法的原理和实现，展示了两个使用场景的示例代码。KMP算法可以应用于各种需要字符串查找和匹配的场合，是一种非常实用的算法。