KMP 算法：高效字符串匹配的核心逻辑

一、为什么需要 KMP？

解决字符串模式匹配问题：在主串S（长度n）中查找模式串T（长度m）的起始位置，核心优势是主串指针不回溯，规避暴力匹配（O(n×m)）的低效，时间复杂度优化至O(n+m)。

KMP 算法的突破在于：匹配失败时，主串指针不回溯，仅通过模式串自身的结构信息调整模式串指针，将时间复杂度降至 O(n + m) 。

二、核心思想：利用 "最长公共前后缀" 避免回溯

1. 关键概念：前缀、后缀与公共长度

前缀：模式串中，从第一个字符开始的连续子串（如 "ABC"的前缀为 "A"、"AB"）。
后缀：模式串中，以最后一个字符结尾的连续子串（如 "ABC"的后缀为 "C"、"BC"）。
最长公共前后缀：前缀与后缀中长度最长的相同子串（如 "ABAB"的最长公共前后缀为 "AB"，长度为 2）。

2. next 数组：模式串的 "回溯指南"

next数组是 KMP 的核心，为模式串 T 预处理得到：

\text{next}[i] 表示模式串前 i+1 个字符（子串 T[0..i] ）的最长公共前后缀长度。
作用：当 T[i] 与主串匹配失败时，模式串指针直接跳至 \text{next}[i-1] ，无需回溯主串。

示例：模式串 "ABCDABD"的 next数组（索引从 0 开始）：

i （字符索引）	0	1	2	3	4	5	6
T[i] （字符）	A	B	C	D	A	B	D
\text{next}[i]	-1	0	0	0	0	1	2

（注： \text{next}[0] = -1 是约定，标识模式串首位匹配失败时主串直接后移）

三、next 数组的计算方法

通过递推计算，利用已求的 next值推导新值，避免重复计算：

初始化： j = 0 （当前计算索引）， k = -1 （最长公共前后缀长度）， \text{next}[0] = -1 。
循环计算（ j 从 1 到 m-1 ）：

若 k = -1 或 T[j] == T[k] ，则 j++ ， k++ ， \text{next}[j] = k 。
否则， k = \text{next}[k] （回溯 k ，寻找更短公共前后缀）。

四、KMP 匹配过程

初始化主串指针 i = 0 ，模式串指针 j = 0 。
循环匹配：

若 S[i] == T[j] ，则 i++ ， j++ （继续匹配下一位）。
若 j = -1 （模式串指针已回溯到起点），则 i++ ， j++ （主串后移，模式串从头开始）。
否则（匹配失败）， j = \text{next}[j] （模式串按 next回溯，主串不回退）。

若 j == m ，匹配成功，返回起始位置 i - j ；否则返回 - 1。

五、基础版 C 语言实现

#include <stdio.h>
#include <string.h>

// 计算模式串T的next数组
void getNext(char* T, int* next, int m) {
    int j = 0, k = -1;
    next[0] = -1;
    while (j < m - 1) {
        if (k == -1 || T[j] == T[k]) {
            j++; k++;
            next[j] = k;
        } else {
            k = next[k]; // 回溯k
        }
    }
}

// KMP匹配：返回模式串在主串中的起始索引（-1表示未找到）
int kmpSearch(char* S, int n, char* T, int m, int* next) {
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || S[i] == T[j]) {
            i++; j++;
        } else {
            j = next[j]; // 模式串回溯
        }
    }
    return (j == m) ? (i - j) : -1;
}

int main() {
    char S[] = "ABCABCDABABCDABCDABDE";
    char T[] = "ABCDABD";
    int n = strlen(S), m = strlen(T);
    int next[m];

    getNext(T, next, m);
    int pos = kmpSearch(S, n, T, m, next);

    if (pos != -1) {
        printf("匹配起始位置：%d\n", pos); // 输出：6
    } else {
        printf("未找到匹配\n");
    }
    return 0;
}

六、时空复杂度分析

时间复杂度：
- 预处理 next数组：遍历模式串一次， O(m) 。
- 匹配过程：主串指针仅前移， O(n) 。
  
  总复杂度： O(n + m) 。
空间复杂度：
- 存储 next数组，大小为 m ，故 O(m) 。

总结

KMP 算法通过 next数组记录模式串的结构特征，实现了主串无回溯的高效匹配。核心是理解 "最长公共前后缀" 如何指导模式串回溯，这一思想也为其他字符串算法提供了启发。

补充（伪代码）

// 计算模式串P的next数组（存储最长公共前后缀长度）
function computeNext(P):
    M = length of P  // 模式串长度
    next = array of length M  // 结果数组
    j = 0  // 记录当前最长公共前后缀的长度
    next[0] = 0  // 第一个字符无前后缀，长度为0
  
    // 从第二个字符开始计算（i从1到M-1）
    for i from 1 to M-1:
        // 若当前字符不匹配，回溯j到上一个可能的公共长度
        while j > 0 and P[i] != P[j]:
            j = next[j-1]
        // 若匹配，延长公共长度
        if P[i] == P[j]:
            j = j + 1
        // 记录当前位置的最长公共前后缀长度
        next[i] = j
    return next


// KMP匹配：在主串S中查找模式串P，返回匹配起始位置（-1表示未找到）
function kmpSearch(S, P, next):
    N = length of S  // 主串长度
    M = length of P  // 模式串长度
    i = 0  // 主串指针（只前移，不回溯）
    j = 0  // 模式串指针（不匹配时回溯）
  
    // 遍历主串和模式串
    while i < N and j < M:
        // 字符匹配，双指针同时后移
        if S[i] == P[j]:
            i = i + 1
            j = j + 1
        // 字符不匹配
        else:
            // 模式串指针非0，根据next数组回溯
            if j != 0:
                j = next[j-1]
            // 模式串指针为0（第一个字符就不匹配），主串指针后移
            else:
                i = i + 1
  
    // 若模式串完全匹配，返回起始位置；否则返回-1
    if j == M:
        return i - M
    else:
        return -1

目录CONTENT

KMP 算法