KMP 算法

1. KMP 算法简介

KMP 算法（Knuth-Morris-Pratt）是一种字符串匹配算法，由 Donald Knuth、 Vaughan Pratt 和 James H. Morris 于 1977 年提出。它用于解决在一个主字符串中寻找子字符串的问题，并且其核心思想是通过利用已经匹配过的信息来避免不必要的比较，从而提高匹配效率。

传统的朴素匹配算法会每次将模式字符串与目标字符串的每个子串进行比较，即使在某些位置已经匹配过，也会重新进行匹配，导致时间复杂度较高。KMP 算法通过计算前缀表（也叫做部分匹配表）来实现对已经匹配信息的利用，从而优化了匹配过程。

1.1 KMP 算法的基本思想

KMP 算法通过“部分匹配”的概念，减少了无谓的字符比较。当目标字符串和模式字符串某一部分匹配失败时，KMP 会根据前缀信息“跳过”一些字符，而不是像朴素算法那样从头开始重新匹配。

具体来说，KMP 算法通过以下步骤完成匹配：

计算模式字符串的部分匹配表（又称前缀表）。
使用该表来加速目标字符串与模式字符串的匹配过程。

1.2 部分匹配表（前缀表）

前缀表的关键是记录模式字符串的每个位置的前缀和后缀相等的最长长度。部分匹配表帮助我们在某一位置匹配失败后，能够跳过一些字符进行重新匹配，而不是重新从头开始。

前缀表的构造过程：

前缀表的每一项表示模式字符串的某个位置之前的子串的“最大前缀后缀相等长度”。
对于每一个位置，前缀表记录模式字符串从开始到该位置的最长前缀（即前缀也是后缀的长度）。

1.3 KMP 算法的时间复杂度

KMP 算法的时间复杂度是 O(n + m)，其中 n 为目标字符串的长度，m 为模式字符串的长度。

O(n) 是因为目标字符串只需要遍历一次。
O(m) 是因为模式字符串的部分匹配表也需要计算一次。

相比于朴素算法的 O(n * m)，KMP 在性能上有了显著的提升。

2. KMP 算法的实现步骤

2.1 计算部分匹配表（前缀表）

部分匹配表的每一项记录模式字符串中某个位置之前，前缀和后缀相等的最长长度。构建这个表的目的是为了加速后续匹配过程，避免从头开始重复比较。

2.2 字符串匹配

在得到前缀表后，我们可以利用该表进行匹配。当在某一位置进行匹配失败时，利用前缀表来决定模式字符串应该向右移动多少个位置，而不需要从头重新匹配。

3. KMP 算法的 Java 实现

以下是 KMP 算法的 Java 代码实现：

public class KMP {

    // 计算部分匹配表
    public static int[] buildPartialMatchTable(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m]; // Longest Prefix Suffix array
        int len = 0; // 当前最长前缀后缀的长度
        int i = 1;
        
        // lps[0] 是0, 因为第一个字符没有前缀和后缀
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len > 0) {
                    len = lps[len - 1];  // 使用已知的最长前缀后缀
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP 主算法
    public static int KMPSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        // 计算部分匹配表
        int[] lps = buildPartialMatchTable(pattern);

        int i = 0;  // 文本字符串的位置
        int j = 0;  // 模式字符串的位置

        // 开始匹配
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                // 找到匹配的子串
                return i - j;
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                // 匹配失败
                if (j > 0) {
                    j = lps[j - 1]; // 使用部分匹配表调整位置
                } else {
                    i++;
                }
            }
        }
        return -1; // 如果没有匹配到，返回 -1
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int result = KMPSearch(text, pattern);
        
        if (result != -1) {
            System.out.println("Pattern found at index: " + result);
        } else {
            System.out.println("Pattern not found.");
        }
    }
}

3.1 代码解释

buildPartialMatchTable 方法：该方法用于计算部分匹配表，它利用两个指针 i 和 len 来遍历模式字符串，并计算每个位置的最长前缀后缀长度。
KMPSearch 方法：该方法用于执行 KMP 算法来进行字符串匹配。在匹配过程中，若发现字符匹配失败，它会根据部分匹配表调整模式字符串的位置，从而跳过不必要的字符比较。