深入理解KMP算法（C语言实现字符串高效匹配的完整教程）

KMP算法的关键：构建 next 数组

KMP算法的核心是 next 数组（也叫部分匹配表）。它记录了模式串中每个位置之前的子串的“最长相等前后缀长度”。

例如，模式串 "ABABC"：

• 位置 0（'A'）：无前缀后缀 → next[0] = -1 或 0（不同实现方式）
• 位置 1（'B'）：前缀 "A"，后缀 "B" → 不相等 → next[1] = 0
• 位置 2（'A'）：前缀 "AB"，后缀 "BA" → 最长相等前后缀为 "A"（长度1）→ next[2] = 1
• 位置 3（'B'）：前缀 "ABA"，后缀 "BAB" → 最长相等前后缀为 "AB"（长度2）→ next[3] = 2
• 位置 4（'C'）：前缀 "ABAB"，后缀 "BABC" → 无相等 → next[4] = 0

C语言实现 KMP 算法

下面我们用 C 语言完整实现 KMP 算法，包括 getNext 函数和 kmpSearch 函数。

#include <stdio.h>#include <string.h>// 构建 next 数组void getNext(char* pattern, int* next) {    int len = strlen(pattern);    next[0] = -1;  // 通常设为 -1，便于后续处理    int i = 0, j = -1;    while (i < len - 1) {        if (j == -1 || pattern[i] == pattern[j]) {            i++;            j++;            next[i] = j;        } else {            j = next[j];        }    }}// KMP 主搜索函数int kmpSearch(char* text, char* pattern) {    int textLen = strlen(text);    int patLen = strlen(pattern);    if (patLen == 0) return 0;    int* next = (int*)malloc(sizeof(int) * patLen);    getNext(pattern, next);    int i = 0, j = 0;    while (i < textLen && j < patLen) {        if (j == -1 || text[i] == pattern[j]) {            i++;            j++;        } else {            j = next[j];        }    }    free(next);    if (j == patLen) {        return i - j;  // 返回首次匹配位置    }    return -1;  // 未找到}// 测试函数int main() {    char text[] = "ABABDABACDABABCABCABC";    char pattern[] = "ABABC";    int pos = kmpSearch(text, pattern);    if (pos != -1) {        printf("模式串在主串中的位置: %d\n", pos);    } else {        printf("未找到匹配的子串\n");    }    return 0;}

代码说明

• getNext 函数使用双指针技巧构建 next 数组，时间复杂度 O(m)。
• kmpSearch 函数利用 next 数组进行匹配，主串指针 i 从不回退，时间复杂度 O(n)。
• 整体时间复杂度为 O(n + m)，空间复杂度为 O(m)（用于存储 next 数组）。

总结

通过本教程，你已经掌握了 KMP算法 的基本原理和 C语言字符串匹配 的完整实现。KMP 是面试和实际开发中非常重要的 字符串查找算法，尤其适用于大文本中的模式匹配场景。

记住，理解 next 数组的构建逻辑是掌握 KMP 的关键。多动手写几遍代码，加深理解！

希望这篇关于 模式匹配优化 的教程对你有帮助！