1. KMP 算法介绍

KMP 算法：全称 「Knuth Morris Pratt 算法」，由 Donald Knuth、James H. Morris、Vaughan Pratt 在 1977 年联合发表。

KMP 算法思想：对于给定文本串 TT 和模式串 PP，当发现文本串的某个字符与模式串失配时，利用模式串的部分匹配信息尽量减少匹配次数，避免文本串的指针回退。

1.1 朴素匹配算法的缺陷

在朴素匹配算法中，分别用指针 ii 和 jj 表示文本串 TT 和模式串 PP 的当前匹配位置。当字符失配时：

  • jj 回退到起始位置；
  • ii 回退到匹配开始位置的下一个字符，重新进行匹配。

示例图展示了朴素匹配算法的过程（失配后重新尝试从下一字符开始匹配）：

朴素匹配算法

在这种情况下，如果匹配字符较多且发生多次失配，匹配效率会很低。

1.2 KMP 算法的改进

KMP 算法通过预处理模式串 PP，构造一个 前缀表（lps 表），在匹配过程中借助前缀表的信息优化模式串指针的移动，使得主串指针 ii 无需回退。

以示例为例：

  • 模式串 P 在匹配时，若在 j=5j=5 处失配：
    • 已知 T[i:i+5]==P[0:5]T[i:i+5] == P[0:5]；
    • 根据前缀表信息，模式串的前缀和后缀存在部分相等，如下图蓝色部分表示：
      KMP 匹配算法移动过程
    • 可直接将模式串指针 jj 回退至前缀表中记录的位置（避免主串回退）。

2. KMP 算法的关键数据结构

2.1 前缀表（lps）

前缀表（lps 表，Longest Prefix Suffix）用于存储模式串的部分匹配信息。

  • 定义：lps[j] 表示模式串 PP 中以第 jj 个字符结尾的子串 P[0:j]P[0:j] 的最长相等前后缀的长度。

示例：P = "ABCABCD"

子串 前缀 后缀 最长相等前后缀长度
A - - 0
AB A B 0
ABC AB BC 0
ABCA A A 1
ABCAB AB AB 2
ABCABC ABC ABC 3
ABCABCD ABCA BCD 0

前缀表 lps 为：[0, 0, 0, 1, 2, 3, 0]。

3. KMP 算法步骤

3.1 前缀表（lps）的构造

构造 lps 表的逻辑如下：

  1. 初始化两个指针：
    • length：表示当前匹配的最长前缀长度；
    • i：遍历模式串 PP 的后缀位置（从索引 1 开始）。
  2. 如果 P[length] == P[i]，更新 lps[i] = length + 1 并移动指针。
  3. 如果失配，length 回退到 lps[length - 1]。
  4. 重复以上步骤直至模式串遍历完毕。

3.2 KMP 匹配过程

  1. 初始化两个指针：
    • i：指向文本串 TT 的当前匹配位置；
    • j：指向模式串 PP 的当前匹配位置。
  2. 若 T[i] == P[j]，同时移动 i 和 j。
  3. 若失配，利用 lps 表调整模式串位置：j = lps[j - 1]。
  4. 若 j == P.length，说明模式串完全匹配，返回匹配起始位置 i - j + 1。
  5. 若文本串遍历完毕仍未匹配，返回 -1。

4. KMP 算法代码实现

Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 构造前缀表（lps 表）
def generateLPS(p: str):
    m = len(p)
    lps = [0] * m
    length = 0  # 最长前缀长度
    i = 1       # 遍历位置

    while i < m:
        if p[i] == p[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length > 0:
                length = lps[length - 1]  # 回退
            else:
                lps[i] = 0
                i += 1
    return lps

# KMP 匹配算法
def kmp(T: str, P: str) -> int:
    n, m = len(T), len(P)
    if m == 0:
        return 0

    lps = generateLPS(P)
    i = j = 0

    while i < n:
        if T[i] == P[j]:
            i += 1
            j += 1
        if j == m:
            return i - j
        elif i < n and T[i] != P[j]:
            if j > 0:
                j = lps[j - 1]  # 回退模式串
            else:
                i += 1
    return -1

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    // KMP 主函数：查找模式串 P 在文本串 T 中的第一个匹配位置
    public int strStr(String T, String P) {
        int n = T.length(); // 文本串长度
        int m = P.length(); // 模式串长度
        if (m == 0) return 0; // 如果模式串为空，直接返回 0

        int[] lps = generateLPS(P); // 构造前缀表
        int j = 0; // 模式串指针

        for (int i = 0; i < n; i++) { // 遍历文本串
            while (j > 0 && T.charAt(i) != P.charAt(j)) {
                j = lps[j - 1]; // 匹配失败时，回退模式串指针
            }
            if (T.charAt(i) == P.charAt(j)) {
                j++; // 匹配成功，移动模式串指针
            }
            if (j == m) {
                return i - m + 1; // 完全匹配，返回起始位置
            }
        }
        return -1; // 遍历结束未找到匹配，返回 -1
    }

    // 前缀表（lps 表）构造函数
    private int[] generateLPS(String P) {
        int m = P.length(); // 模式串长度
        int[] lps = new int[m];
        int length = 0; // 表示当前匹配的最长前缀长度
        int i = 1; // 遍历模式串，从索引 1 开始

        while (i < m) {
            if (P.charAt(i) == P.charAt(length)) {
                length++;
                lps[i] = length; // 更新 lps 表
                i++;
            } else {
                if (length > 0) {
                    length = lps[length - 1]; // 回退
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // 测试代码
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.strStr("sadbutsad", "sad"));     // 输出 0
        System.out.println(solution.strStr("leetcode", "leeto"));   // 输出 -1
        System.out.println(solution.strStr("mississippi", "issi")); // 输出 1
        System.out.println(solution.strStr("aaaaa", "bba"));        // 输出 -1
    }
}

代码解析

1. 前缀表构造

  • 方法：generateLPS：
    • 使用双指针 i 和 length：
      • i 遍历模式串；
      • length 表示当前匹配的最长前缀长度。
    • 如果匹配成功（P[i] == P[length]），更新 lps[i] = length + 1，并移动指针。
    • 如果失配，根据前缀表回退：length = lps[length - 1]。

2. 匹配过程

  • 方法：strStr：
    • 使用双指针 i 和 j：
      • i 遍历文本串；
      • j 遍历模式串。
    • 匹配失败时，模式串指针 j 回退：j = lps[j - 1]。
    • 如果 j == m（模式串完全匹配），返回匹配的起始位置 i - m + 1。

运行示例

运行代码后，输出结果：

1
2
3
4
0
-1
1
-1

5.时间复杂度分析

  • 前缀表构造：O(m)O(m)，模式串长度为 mm。
  • 匹配过程：O(n)O(n)，文本串长度为 nn。
  • 总复杂度：O(n+m)O(n + m)。

KMP 算法的效率大大优于朴素匹配算法，特别是在长文本串和长模式串的情况下。

6.相关题目

28. 找出字符串中第一个匹配项的下标