C语言字符串匹配算法详解（从零开始掌握字符串查找与模式匹配）

什么是字符串匹配？

字符串匹配（也称为 模式匹配）是指在一个主串（text）中查找是否存在一个子串（pattern），如果存在，返回其起始位置。例如：

• 主串："Hello, welcome to C programming!"
• 模式串："C programming"
• 匹配结果：起始位置为 18（从0开始计数）

1. 暴力匹配算法（Brute Force）

这是最简单直观的方法：逐个字符比较，若不匹配则主串回退，模式串重置。

#include <stdio.h>#include <string.h>// 暴力匹配函数int bruteForceSearch(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[] = "Hello, welcome to C programming!";    char pattern[] = "C programming";    int pos = bruteForceSearch(text, pattern);    if (pos != -1) {        printf("匹配成功！位置：%d\n", pos);    } else {        printf("未找到匹配。\n");    }    return 0;}

暴力法的时间复杂度为 O(n×m)，在最坏情况下效率较低，但代码简单、易于理解，适合初学者入门 C语言编程教程 中的基础内容。

2. KMP 算法（Knuth-Morris-Pratt）

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

核心思想：当发生失配时，利用已匹配部分的信息，跳过不必要的比较。

#include <stdio.h>#include <string.h>// 构建 next 数组void buildNext(const char* pattern, int* next) {    int m = strlen(pattern);    next[0] = -1;    int i = 0, j = -1;    while (i < m - 1) {        if (j == -1 || pattern[i] == pattern[j]) {            i++;            j++;            next[i] = j;        } else {            j = next[j];        }    }}// KMP 匹配函数int kmpSearch(const char* text, const char* pattern) {    int n = strlen(text);    int m = strlen(pattern);    int* next = (int*)malloc(sizeof(int) * m);    buildNext(pattern, next);    int i = 0, j = 0;    while (i < n && j < m) {        if (j == -1 || text[i] == pattern[j]) {            i++;            j++;        } else {            j = next[j];        }    }    free(next);    if (j == m)        return i - j; // 返回匹配起始位置    else        return -1;}int main() {    char text[] = "ABABDABACDABABCABCABC";    char pattern[] = "ABABCABC";    int pos = kmpSearch(text, pattern);    if (pos != -1) {        printf("KMP 匹配成功！位置：%d\n", pos);    } else {        printf("未找到匹配。\n");    }    return 0;}

虽然 KMP 算法理解起来稍有难度，但它是学习高级 模式匹配 技术的重要基石。

总结

无论是简单的暴力匹配，还是高效的 KMP 算法，掌握 C语言字符串匹配 的核心思想，对提升编程能力和解决实际问题都大有裨益。建议初学者先从暴力法入手，再逐步挑战 KMP 等高级算法。

希望这篇 C语言编程教程 能帮助你轻松入门字符串匹配的世界！