KMP 算法中的 LPS 数组

在 KMP 算法中，LPS 数组（Longest Prefix Suffix，最长前缀后缀数组）是其核心部分。通过 LPS 数组，我们能够在匹配过程中跳过不必要的字符，避免了重复比较，从而提高了算法效率。在这一部分的中，我们将详细讲解 LPS 数组的概念、构建方法及其在 KMP 算法中的作用。

1. 什么是 LPS 数组

LPS 数组记录了模式字符串中每个位置之前，最长的相同的前缀和后缀的长度。通过 LPS 数组，我们能够在模式字符串匹配失败时，避免从头开始匹配。具体来说，当匹配失败时，LPS 数组可以告诉我们模式字符串应该向右滑动多少位，避免不必要的比较。

1.1 LPS 数组的含义

LPS 数组的每个元素表示该位置之前，模式字符串的最长前缀和后缀的公共长度。举个简单的例子，如果模式字符串是 AABAACAABAA，那么对于模式中的每个字符，LPS 数组记录了其对应位置的前缀和后缀相同的最大长度。

例如：

• 对于字符 A，没有前缀和后缀相等的部分，LPS 数组的值为 0。
• 对于字符串 AAB，最长前缀和后缀是 A，所以 LPS 数组的值为 1。
• 对于字符串 AABAACAABAA，LPS 数组的值会逐步计算出来，记录了每个字符前面的前缀和后缀的最长公共长度。

2. LPS 数组的构建过程

在 KMP 算法中，LPS 数组的构建是非常关键的步骤。我们从模式字符串的第二个字符开始计算，逐步构建该数组。LPS 数组的构建过程主要依赖于两种情况：

1. 如果当前字符与前一个字符匹配，我们可以通过将前缀长度加 1 来扩展匹配长度。
2. 如果当前字符不匹配，我们将根据前面已经计算的 LPS 数组的值来调整当前匹配的位置。

2.1 构建 LPS 数组的步骤

假设模式字符串为 pattern，长度为 m，我们需要构建一个长度为 m 的 LPS 数组。

• 初始化：LPS 数组的第一个位置始终为 0，因为没有前缀和后缀相同的部分。
• 从第二个字符开始，逐个比较当前字符与前一个匹配的部分的后缀字符：
  • 如果字符匹配，LPS 数组当前值加 1，并继续向下比较。
  • 如果字符不匹配，通过查看 LPS 数组的前一个值，跳过一些已经匹配过的字符，避免重新比较。

2.2 LPS 数组的核心思想

LPS 数组的核心思想是“前缀和后缀相同”的概念。在构建 LPS 数组时，我们需要找到模式字符串中每一位置之前的最长前缀和后缀的匹配长度。通过这种方式，我们在匹配过程中遇到不匹配时，能够跳过一些字符，避免从头开始重新匹配。

3. KMP 算法中的应用

在 KMP 算法中，LPS 数组的作用非常重要。它可以帮助我们在匹配失败时，通过查看已计算出的前缀后缀匹配信息，快速确定模式字符串应该向右滑动多少位置，而无需重新从头开始匹配。具体的匹配过程如下：

1. 我们将模式字符串与目标文本进行逐个字符的比较。
2. 如果字符匹配，则继续向右移动，直到找到匹配的子串或者整个文本结束。
3. 如果字符不匹配，则根据 LPS 数组中的值决定模式字符串的滑动位置。具体地，如果当前字符不匹配，则根据 LPS 数组跳过一些已经匹配过的部分，避免从头开始重新比较。

4. Java 实现 LPS 数组

接下来，我们用 Java 代码来展示如何实现 LPS 数组的构建过程。以下是代码示例：

public class KMP {
    // 构建 LPS 数组
    public static int[] buildLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];  // 存储LPS数组
        int len = 0;  // 当前最长前缀和后缀的长度
        int i = 1;  // 从第二个字符开始

        // 计算 LPS 数组
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;  // 匹配成功，增加长度
                lps[i] = len;  // 更新 LPS 数组
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];  // 根据 LPS 数组的值跳过一些字符
                } else {
                    lps[i] = 0;  // 没有前缀后缀匹配，设置为0
                    i++;
                }
            }
        }
        return lps;  // 返回计算好的 LPS 数组
    }

    public static void main(String[] args) {
        String pattern = "AABAACAABAA";
        int[] lps = buildLPS(pattern);

        // 输出 LPS 数组
        for (int i = 0; i < lps.length; i++) {
            System.out.print(lps[i] + " ");
        }
    }
}

4.1 代码解析：

1. buildLPS 方法用于构建 LPS 数组。我们使用一个 len 变量来记录当前匹配的前缀后缀的长度。如果当前字符匹配，len 增加，记录到 LPS 数组中。如果不匹配，len 根据之前的匹配信息调整，避免重新比较。
2. 在 main 方法中，我们传入一个模式字符串，然后调用 buildLPS 方法得到对应的 LPS 数组，并输出每个元素。

4.2 LPS 数组的输出：

对于模式字符串 AABAACAABAA，输出的 LPS 数组为：

0 1 1 2 1 2 3 4 1 2 3 4

可以看到，在每个位置之前，LPS 数组记录了最长的前缀和后缀相同的部分的长度。例如，位置 4 之前的部分是 AABA，最长的前缀后缀相同的部分是 A，所以 LPS[4] 为 1。

5. KMP 算法的时间复杂度

通过构建 LPS 数组，KMP 算法在匹配过程中不再进行重复的比较，从而大大提高了效率。整个 KMP 算法的时间复杂度为 O(n + m)，其中：

• n 为目标文本的长度，
• m 为模式字符串的长度。

构建 LPS 数组的时间复杂度为 O(m)，匹配过程的时间复杂度为 O(n)，因此 KMP 算法的总时间复杂度为 O(n + m)。

6. 总结

今天我们详细讲解了 KMP 算法中的 LPS 数组及其作用。LPS 数组通过记录模式字符串中每个位置之前最长前缀和后缀的公共部分长度，使得在匹配过程中可以避免重复比较，从而提升匹配效率。通过一个具体的 Java 代码示例，我们展示了如何构建 LPS 数组，并且解析了它在 KMP 算法中的应用。希望通过这节课的学习，大家对 KMP 算法及其优化有了更深刻的理解。