C语言字符串匹配算法详解（从暴力匹配到KMP算法的完整实现）

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

暴力匹配是最直观的方法：逐个字符比较，若不匹配则主串回退，模式串重置。虽然简单，但效率较低，时间复杂度为 O(m×n)，其中 m 是主串长度，n 是模式串长度。

#include <stdio.h>#include <string.h>// 暴力匹配算法int bruteForceSearch(char* text, char* pattern) {    int i = 0; // 主串索引    int j = 0; // 模式串索引    while (i < strlen(text) && j < strlen(pattern)) {        if (text[i] == pattern[j]) {            i++;            j++;        } else {            i = i - j + 1; // 主串回退            j = 0;         // 模式串重置        }    }    if (j == strlen(pattern)) {        return i - j; // 返回匹配起始位置    }    return -1; // 未找到}int main() {    char text[] = "ababcababa";    char pattern[] = "ababa";    int pos = bruteForceSearch(text, pattern);    if (pos != -1) {        printf("匹配成功，位置：%d\n", pos);    } else {        printf("未找到匹配\n");    }    return 0;}

方法二：KMP算法（Knuth-Morris-Pratt）

KMP算法是一种高效的字符串查找算法，它通过预处理模式串构建“部分匹配表”（也称 next 数组），避免主串指针回退，从而将时间复杂度优化到 O(m+n)。

KMP的核心思想是：当发生失配时，利用已匹配部分的信息，让模式串尽可能向右滑动，而不是从头开始匹配。

步骤1：构建 next 数组

void computeLPSArray(char* pattern, int M, int* lps) {    int len = 0; // 最长公共前后缀长度    lps[0] = 0;  // 第一个字符的lps值为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++;            }        }    }}

步骤2：使用 next 数组进行匹配

int KMPSearch(char* text, char* pattern) {    int M = strlen(pattern);    int N = strlen(text);    // 创建 lps[] 数组，用于存储最长前缀后缀长度    int lps[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) {            return i - j; // 找到匹配            j = lps[j - 1];        } else if (i < N && pattern[j] != text[i]) {            if (j != 0)                j = lps[j - 1];            else                i++;        }    }    return -1; // 未找到}

为什么选择KMP？

对于大规模文本处理（如搜索引擎、DNA序列分析），暴力匹配效率太低。而模式匹配C语言实现中，KMP算法因其线性时间复杂度成为工业级应用的首选。掌握KMP不仅提升编程能力，也是面试高频考点。

总结

本文详细讲解了两种主流的C语言字符串匹配算法：暴力匹配和KMP算法。我们提供了完整的可运行代码，并解释了每一步的逻辑。建议初学者先理解暴力匹配，再挑战KMP。多动手实践，你将能灵活运用这些字符串查找算法解决实际问题。

提示：你可以将上述代码复制到本地IDE（如Code::Blocks或VS Code）中编译运行，观察输出结果，加深理解。