C语言中的字符串匹配算法（从暴力匹配到KMP，小白也能轻松掌握）

方法一：暴力匹配（Brute Force）

这是最直观的方法：从主串的每一个位置开始，逐个字符与模式串比较。一旦发现不匹配，就向右移动一位，重新开始比较。

优点：简单易懂。
缺点：效率低，最坏时间复杂度为 O(n×m)，其中 n 是主串长度，m 是模式串长度。

下面是 C 语言实现的暴力匹配代码：

#include <stdio.h>#include <string.h>// 暴力匹配函数int bruteForceMatch(const char* text, const char* pattern) {    int n = strlen(text);    int m = strlen(pattern);        for (int i = 0; i <= n - m; i++) {        int j;        for (j = 0; j < m; j++) {            if (text[i + j] != pattern[j])                break;        }        if (j == m) // 完全匹配            return i; // 返回起始位置    }    return -1; // 未找到}int main() {    char text[] = "ABABDABACDABABCABCABCABCABC";    char pattern[] = "ABABCABC";        int pos = bruteForceMatch(text, pattern);    if (pos != -1)        printf("匹配成功！位置：%d\n", pos);    else        printf("未找到匹配。\n");        return 0;}

方法二：KMP 算法（高效匹配）

KMP（Knuth-Morris-Pratt）算法是一种线性时间的字符串匹配算法，时间复杂度为 O(n + m)。它的核心思想是：当发生不匹配时，利用已匹配部分的信息，避免回退主串指针。

关键在于构建一个“部分匹配表”（也叫 next 数组），记录模式串中每个位置之前的子串的最长相同前后缀长度。

Step 1：构建 next 数组

void computeLPSArray(const char* pattern, int m, int* lps) {    int len = 0; // 当前最长相同前后缀长度    lps[0] = 0; // 第一个字符没有前缀    int i = 1;        while (i < m) {        if (pattern[i] == pattern[len]) {            len++;            lps[i] = len;            i++;        } else {            if (len != 0) {                len = lps[len - 1]; // 回退            } else {                lps[i] = 0;                i++;            }        }    }}

Step 2：使用 next 数组进行匹配

int kmpSearch(const char* text, const char* pattern) {    int n = strlen(text);    int m = strlen(pattern);        // 创建 LPS（最长前缀后缀）数组    int* lps = (int*)malloc(sizeof(int) * m);    computeLPSArray(pattern, m, lps);        int i = 0; // text 的索引    int j = 0; // pattern 的索引        while (i < n) {        if (pattern[j] == text[i]) {            i++;            j++;        }                if (j == m) {            free(lps);            return i - j; // 匹配成功，返回起始位置        } else if (i < n && pattern[j] != text[i]) {            if (j != 0)                j = lps[j - 1]; // 利用 next 数组跳过已知匹配部分            else                i++;        }    }        free(lps);    return -1; // 未找到}

完整程序可将上述两个函数整合，并在 main 函数中调用 kmpSearch。你会发现，即使面对大量重复字符（如 "AAAAA..." 中找 "AAAAB"），KMP 依然高效，而暴力法会严重退化。

总结

今天我们学习了两种C语言字符串匹配方法：

• 暴力匹配：简单但慢，适合小数据或教学理解；
• KMP算法：高效且经典，是模式匹配入门必学内容。

掌握这些字符串查找算法，不仅能提升编程能力，还能为后续学习正则表达式引擎、编译原理打下基础。建议你动手敲一遍代码，加深理解！

希望这篇教程让你对KMP算法详解不再感到畏惧。编程路上，每一步都算数！