Java数据结构之KMP算法的实现

1. KMP算法的概述

KMP算法的全称是Knuth-Morris-Pratt算法，是一种字符串匹配算法，用于在文本串S内查找一个模式串P的出现位置。它的特点是在P和S两个序列中，当匹配失败时，它会跳过P的部分已匹配的字符，利用这个信息来减少S和P之间的匹配次数，从而提高匹配效率。

2. KMP算法的实现

2.1 预处理失配函数

KMP算法中的一个重要概念是前缀和后缀。对于一个字符串P，它的前缀是指从第一个字符开始，一直到某一位置的子串。例如，对于字符串“abcd”，它的前缀包括“a”、“ab”、“abc”和“abcd”。后缀则是从某一位置往后，一直到最后一个字符的子串。例如，对于字符串“abcd”，它的后缀包括“d”、“cd”、“bcd”和“abcd”。

失配函数（也称为部分匹配表）是KMP算法中的核心，它记录了模式串每一位在匹配失败时，应该跳过的最长前缀和后缀。具体的，假设我们已经得到了字符串P的失配函数mp，它可以通过以下方法计算得到：

private static int[] buildNext(String p) {
    int[] next = new int[p.length()];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < p.length() - 1) {
        if (j == -1 || p.charAt(i) == p.charAt(j)) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

下面是计算“ababc”的失配函数的过程：

 a b a b c
 -1 0 0 1 2

对于位置i，失配函数mp[i]，表示p[0]~p[mp[i] - 1]和p[i - mp[i] + 1]~p[i]这两个段的字符是相同的。

2.2 匹配过程

在计算出失配函数之后，我们就可以在字符串S中查找模式串P了。具体的流程如下：

1. 定义两个指针i和j，分别指向S和P中的当前字符
2. 如果S[i] == P[j]，则i和j都往后移动继续匹配
3. 如果S[i] != P[j]，则根据失配函数mp[j]更新j的位置，并继续和S[i]匹配
4. 如果j已经到达P的末尾，则表示匹配成功，返回i - j的值，即匹配到的位置，否则返回-1，表示匹配失败

下面是对字符串“abcabcababc”的匹配过程：

    S: a b c a b c a b a b c
        |           |
    P: a b c a b c a b a b c
        |           |
mp[j]:-1 0 0 1 2 3 4 2 0 1 2

可以看到，在S的第8个字符出现匹配失败时，我们根据失配函数mp[j]更新j的位置到4（即P的第5个字符），然后继续和S[i]匹配，直到匹配成功。

3. 示例说明

下面是两个例子，演示了如何使用Java实现KMP算法：

3.1 示例1

假设我们需要在字符串“ababcabcababdef”中查找模式串“abcab”的位置。可以使用以下代码：

public static void main(String[] args) {
    String s = "ababcabcababdef";
    String p = "abcab";
    int pos = kmp(s, p);
    System.out.println(pos);
}

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

3.2 示例2

假设我们需要在文本文件中查找所有包含字符串“abcab”的行，可以使用以下代码：

public static void main(String[] args) throws IOException {
    String p = "abcab";
    BufferedReader reader = new BufferedReader(new FileReader("input.txt"));
    String line;
    while ((line = reader.readLine()) != null) {
        int pos = kmp(line, p);
        if (pos != -1) {
            System.out.println(line);
        }
    }
    reader.close();
}

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

这个例子中，我们使用了Java的输入输出流来读取文件中的每一行，并对每一行进行KMP匹配操作，查找所有包含模式串的行。注意，这个代码只是提供了一种示例，实际上在处理大型文本文件时，我们需要使用更高效的技术来进行匹配，例如AC自动机等。