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

步骤一：构建next数组

next数组是KMP算法的关键。对于模式串 pattern，next[i] 表示子串 pattern[0..i-1] 的最长相等前后缀的长度。

例如，模式串 "ABABC" 的 next 数组为：

• next[0] = -1（约定）
• next[1] = 0（"A" 没有真前缀/后缀）
• next[2] = 0（"AB" 前后缀不相等）
• next[3] = 1（"ABA" 的最长相同前后缀是 "A"）
• next[4] = 2（"ABAB" 的最长相同前后缀是 "AB"）

下面是C语言实现next数组的函数：

void buildNext(char* pattern, int* next) {    int len = strlen(pattern);    next[0] = -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匹配函数

有了next数组，我们就可以进行高效的字符串匹配了。主串指针永不回退，只根据next数组调整模式串的位置。

int kmpSearch(char* text, char* pattern) {    int textLen = strlen(text);    int patLen = strlen(pattern);    if (patLen == 0) return 0;    int* next = (int*)malloc(patLen * sizeof(int));    buildNext(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; // 未找到}  

完整示例程序

下面是一个完整的C语言程序，演示如何使用KMP算法进行字符串匹配：

#include <stdio.h>#include <string.h>#include <stdlib.h>void buildNext(char* pattern, int* next) {    int len = strlen(pattern);    next[0] = -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];        }    }}int kmpSearch(char* text, char* pattern) {    int textLen = strlen(text);    int patLen = strlen(pattern);    if (patLen == 0) return 0;    int* next = (int*)malloc(patLen * sizeof(int));    buildNext(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[] = "ABABDABACDABABCABCABCABC";    char pattern[] = "ABABC";    int pos = kmpSearch(text, pattern);    if (pos != -1) {        printf("Pattern found at index %d\n", pos);    } else {        printf("Pattern not found\n");    }    return 0;}  

总结

KMP算法是高效字符串搜索的经典代表。通过预处理模式串生成next数组，KMP避免了主串指针回溯，显著提升了匹配效率。掌握KMP不仅有助于解决实际问题（如文本编辑器中的查找功能），也是面试中常见的算法题。

希望这篇关于C语言字符串匹配的教程能帮助你理解KMP算法。动手敲一遍代码，你会对它的精妙之处有更深体会！

记住我们的核心关键词：KMP算法、C语言字符串匹配、KMP模式匹配、高效字符串搜索。它们是你进一步学习和搜索相关资料的重要线索。