2025-05-30

kmp

KMP 算法：字符串匹配的艺术

1. 为什么需要 KMP？暴力匹配的痛点

让我们先回顾一下暴力匹配（Brute Force）是如何工作的。假设主串 text = "ABABCABABAB"，模式串 pattern = "ABAB"。

text:    A B A B C A B A B A B
pattern: A B A B
         ^
         (匹配A)

text:    A B A B C A B A B A B
pattern: A B A B
           ^
           (匹配B)

text:    A B A B C A B A B A B
pattern: A B A B
             ^
             (匹配A)

text:    A B A B C A B A B A B
pattern: A B A B
               ^
               (匹配B)

text:    A B A B C A B A B A B
pattern: A B A B
                 ^
                 (匹配C 与 B 不匹配，模式串整体后移一位，从头开始比较)

text:    A B A B C A B A B A B
pattern:   A B A B
           ^
           (重新从头开始比较)
...

当发生不匹配时，暴力匹配会将模式串整体向后移动一位，并重新从模式串的第一个字符开始与主串当前位置的字符进行比较。在最坏情况下（例如 text = "AAAAAAAAB", pattern = "AAAB"），暴力匹配会进行大量的重复比较，导致时间复杂度高达 O(mn)。

观察上述过程，我们发现一个问题：当 pattern[j] 与 text[i] 不匹配时，我们已经知道 text[i-j ... i-1] 和 pattern[0 ... j-1] 是匹配的。暴力匹配却直接抛弃了这些已匹配的信息，从头再来。KMP 算法正是利用了这些已匹配的信息，避免了主串指针 i 的回溯，从而提高了效率。

2. KMP 算法的核心思想：利用“前缀”和“后缀”

KMP 算法的关键在于，当模式串与主串发生不匹配时，它不回溯主串的指针，而是根据模式串自身的特点，将模式串向右滑动尽可能远的距离。这个距离的计算依赖于模式串的**“最长公共前后缀”**信息。

什么是“最长公共前后缀”？

对于模式串的任意一个前缀 pattern[0 ... j-1]（即 pattern 的一个子串），我们想找到一个最长的真前缀（不包括整个子串本身）和最长的真后缀（不包括整个子串本身）是相同的。

例如，模式串 pattern = "ABABA"：

当子串是 "A" 时：无公共前后缀。
当子串是 "AB" 时：无公共前后缀。
当子串是 "ABA" 时：前缀 A，后缀 A。最长公共前后缀长度为 1。
当子串是 "ABAB" 时：前缀 A，后缀 B。前缀 AB，后缀 AB。最长公共前后缀长度为 2。
当子串是 "ABABA" 时：前缀 A，后缀 A。前缀 AB，后缀 BA。前缀 ABA，后缀 ABA。最长公共前后缀长度为 3。

KMP 算法预处理模式串，生成一个 next 数组（也常被称为 lps 数组，即 Longest Proper Prefix which is also Suffix），这个数组记录了模式串每个前缀的最长公共前后缀的长度。

3. `next` 数组（或 `lps` 数组）的构建

next[j] 表示 pattern[0 … j-1] 这个子串的最长公共前后缀的长度。

约定 next[0] = -1 (或 next[0] = 0，取决于实现细节)，表示模式串第一个字符失配时，模式串应整体后移一位。

以 pattern = "ABABCABAB" 为例，我们来手动构建 next 数组：

索引 j	pattern[j]	pattern[0…j] (子串)	最长公共前后缀 (长度)	next[j+1] (模式串下一个位置的值)
-	-	空串	-	`next[0] = -1` (约定)
0	`A`	`A`	空串 (0)	`next[1] = 0`
1	`B`	`AB`	空串 (0)	`next[2] = 0`
2	`A`	`ABA`	`A` (1)	`next[3] = 1`
3	`B`	`ABAB`	`AB` (2)	`next[4] = 2`
4	`C`	`ABABC`	空串 (0)	`next[5] = 0`
5	`A`	`ABabca`	`A` (1)	`next[6] = 1`
6	`B`	`ABabcAB`	`AB` (2)	`next[7] = 2`
7	`A`	`ABabcABA`	`ABA` (3)	`next[8] = 3`
8	`B`	`ABabcABAB`	`ABAB` (4)	`next[9] = 4`

构建 next 数组的算法：

我们可以使用动态规划的思想来构建 next 数组。

设 next[j] 已经计算好，我们来计算 next[j+1]。

next[j+1] 实际是 pattern[0…j] 这个子串的最长公共前后缀长度。

用 k 表示当前已知的最长公共前后缀的长度。初始 k=0。
用 j 遍历模式串的索引。

// 构建 next 数组 (next[i] 表示 pattern[0...i-1] 的最长公共前后缀长度)
// next[0] 通常设为 -1 (或 0)
void computeNextArray(const char* pattern, int m, int* next) {
    next[0] = -1; // 或 next[0] = 0，取决于后续匹配逻辑
    int k = -1;   // k 表示当前已匹配的模式串前缀的长度
    int j = 0;    // j 遍历模式串的索引

    while (j < m - 1) { // 遍历到 pattern 的倒数第二个字符
        // k == -1 (说明k回溯到-1，或者j=0时) 或 pattern[k] == pattern[j]
        if (k == -1 || pattern[k] == pattern[j]) {
            k++; // 匹配成功，前缀长度增加
            j++; // 模式串的当前字符后移
            next[j] = k; // 更新 next 数组
        } else {
            // 不匹配，回溯 k 到 next[k]
            // 这意味着我们尝试用模式串的更短的前缀来匹配
            k = next[k];
        }
    }
}

注意：这里的 next 数组定义是 next[j] 表示 pattern[0…j-1] 的最长公共前后缀的长度，即 pattern[j] 失配时，模式串应该移动到 pattern[next[j]] 处继续比较。

或者，更常见的定义是 next[i] 表示 pattern[0…i] 的最长公共前后缀的长度，那么失配时回溯到 next[j-1]。这里我们采用前者，方便后续匹配。

4. KMP 匹配算法

有了 next 数组，KMP 匹配过程就变得高效了。

i：主串 text 的当前比较位置。
j：模式串 pattern 的当前比较位置。

匹配过程：

当 text[i] 和 pattern[j] 匹配时，i 和 j 同时向后移动一位 (i++, j++)。
当
1
text[i]
和
1
pattern[j]
不匹配时：
- 如果 j > 0（即不是模式串的第一个字符失配），则将 j 更新为 next[j]。这表示我们将模式串向右滑动，使得 pattern[0 ... next[j]-1] 与 text[i - next[j] ... i-1] 保持对齐，然后从 pattern[next[j]] 处开始重新比较。主串指针 i 不回溯。
- 如果 j = 0（即模式串的第一个字符就失配），则只将 i 向后移动一位 (i++)，j 保持为 0（模式串整体后移一位，从头开始比较）。

当 j 等于模式串的长度 m 时，表示找到了一个匹配。此时，text 中匹配的起始位置是 i - m。找到后，为了寻找下一个匹配，我们将 j 更新为 next[j] (即 next[m])，然后继续匹配。

// KMP 字符串匹配算法
// 返回模式串在主串中第一次出现的起始索引，未找到则返回 -1
int kmpSearch(const char* text, const char* pattern) {
    int n = 0; // 主串长度
    while (text[n] != '\0') n++;
    int m = 0; // 模式串长度
    while (pattern[m] != '\0') m++;

    if (m == 0) return 0; // 空模式串总是在0位置匹配
    if (n == 0) return -1; // 空主串无法匹配

    int* next = (int*)malloc(sizeof(int) * m);
    if (next == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    
    // 1. 构建 next 数组
    computeNextArray(pattern, m, next);

    // 2. KMP 匹配过程
    int i = 0; // 主串指针
    int j = 0; // 模式串指针

    while (i < n) {
        // 当 pattern[j] 和 text[i] 匹配时，或 j 已经回溯到 -1 (模式串整体右移)
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            // 不匹配，根据 next 数组移动模式串指针 j
            j = next[j];
        }

        // 找到了一个匹配
        if (j == m) {
            free(next);
            return i - m; // 返回匹配的起始位置
        }
    }

    free(next);
    return -1; // 未找到匹配
}

5. 完整 C 语言代码示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h> // for strlen

// 构建 next 数组 (next[j] 表示 pattern[0...j-1] 的最长公共前后缀长度)
// next[0] 设为 -1
void computeNextArray(const char* pattern, int m, int* next) {
    next[0] = -1; // 哨兵值，表示模式串第一个字符失配时，主串指针 i 向右移，模式串从头开始
    int k = -1;   // k 表示当前已匹配的模式串前缀的长度
    int j = 0;    // j 遍历模式串的索引 (pattern[j] 是当前正在考察的字符)

    while (j < m - 1) { // 遍历到 pattern 的倒数第二个字符
        // 如果 k == -1 (说明模式串已完全回溯，或者 j=0 时)
        // 或者当前考察的字符 pattern[j] 与模式串的第 k 个字符 pattern[k] 相同
        if (k == -1 || pattern[k] == pattern[j]) {
            k++; // 匹配成功，前缀长度 k 增加
            j++; // 模式串的当前字符 j 增加
            next[j] = k; // 更新 next 数组
        } else {
            // 不匹配，回溯 k 到 next[k]
            // 尝试用模式串的更短的前缀来匹配
            k = next[k];
        }
    }
}

// KMP 字符串匹配算法
// 返回模式串在主串中第一次出现的起始索引，未找到则返回 -1
int kmpSearch(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);

    if (m == 0) return 0; // 空模式串总是在0位置匹配
    if (n == 0) return -1; // 空主串无法匹配

    int* next = (int*)malloc(sizeof(int) * m);
    if (next == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    
    // 1. 构建 next 数组
    computeNextArray(pattern, m, next);

    // 2. KMP 匹配过程
    int i = 0; // 主串指针
    int j = 0; // 模式串指针

    while (i < n) {
        // 当 pattern[j] 和 text[i] 匹配时，或 j 已经回溯到 -1 (模式串整体右移)
        if (j == -1 || text[i] == pattern[j]) {
            i++; // 主串指针前进
            j++; // 模式串指针前进
        } else {
            // 不匹配，根据 next 数组移动模式串指针 j
            // 主串指针 i 不回溯
            j = next[j];
        }

        // 找到了一个匹配
        if (j == m) {
            free(next);
            return i - m; // 返回匹配的起始位置 (i 是匹配结束的后一个位置)
        }
    }

    free(next);
    return -1; // 未找到匹配
}

int main() {
    const char* text1 = "ABABCABABAB";
    const char* pattern1 = "ABAB";
    int index1 = kmpSearch(text1, pattern1);
    printf("在 \"%s\" 中查找 \"%s\"，第一次出现位置: %d\n", text1, pattern1, index1); // Expected: 0

    const char* text2 = "ABCDEFGH";
    const char* pattern2 = "FGH";
    int index2 = kmpSearch(text2, pattern2);
    printf("在 \"%s\" 中查找 \"%s\"，第一次出现位置: %d\n", text2, pattern2, index2); // Expected: 5

    const char* text3 = "AAAAAAAAB";
    const char* pattern3 = "AAAB";
    int index3 = kmpSearch(text3, pattern3);
    printf("在 \"%s\" 中查找 \"%s\"，第一次出现位置: %d\n", text3, pattern3, index3); // Expected: 4

    const char* text4 = "HELLO WORLD";
    const char* pattern4 = "XYZ";
    int index4 = kmpSearch(text4, pattern4);
    printf("在 \"%s\" 中查找 \"%s\"，第一次出现位置: %d\n", text4, pattern4, index4); // Expected: -1
    
    const char* text5 = "ABCBABCDABCD";
    const char* pattern5 = "ABCD";
    int index5 = kmpSearch(text5, pattern5);
    printf("在 \"%s\" 中查找 \"%s\"，第一次出现位置: %d\n", text5, pattern5, index5); // Expected: 3

    return 0;
}

6. KMP 算法的优势与复杂度分析

时间复杂度：
- 构建 next 数组：O(m)，其中 m 是模式串的长度。
- 匹配过程：O(n)，其中 n 是主串的长度。主串指针 i 永不回溯，模式串指针 j 最多回溯 m 次（每次回溯都会导致 j 减小），但每次 i 和 j 至少有一个会前进，所以总操作次数是线性的。
- 总时间复杂度：*O(m+n)*。
空间复杂度：
- O(m)，用于存储 next 数组。

与暴力匹配相比，KMP 算法的优势在于： 它在模式串与主串发生不匹配时，能够利用已匹配的模式串前缀信息，避免主串指针的回溯，从而在最坏情况下也能保持线性时间复杂度。这使得它在处理长文本和重复模式的字符串匹配问题时表现出色。

Title:kmp

Author:

Created:2025-05-30, 20:50:56

Updated:2025-05-30, 20:52:04

Full URL:http://example.com/2025/05/30/kmp/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.