C语言学习笔记20260628：字符串子串查找的三种解法

一、学习目标

通过经典的“子串查找”问题，掌握字符串匹配从“暴力模拟”到“工程调用”再到“算法优化”的三种核心范式。深入理解暴力匹配法的底层逻辑，学习标准库函数 strstr 的指针运算技巧，并探究 KMP 算法如何通过“跳转指南（next数组）”避免主串回溯，体会算法思维在性能优化中的巨大作用。

二、问题拆解与核心逻辑

本题要求在长度为 N 的主字符串 str 中，查找长度为 M 的子串 sub 首次出现的起始下标。例如 str = "abcabcd", sub = "abcd"，应返回下标 3。核心约束条件为：

1. 边界处理：需处理子串为空、子串长度大于主串等异常情况。
2. 匹配效率：在大数据量或长文本搜索场景下，暴力法可能面临严重的性能瓶颈。

三、方法一：暴力匹配法（双重循环模拟）

3.1 核心思路

采用双重循环的暴力匹配算法。外层循环遍历主串的每个可能起始位置 i，内层循环从当前起始位置开始，逐个字符与子串进行比对。一旦发现字符不匹配，主串指针 i 回退到本次匹配的下一个位置，子串指针 j 归零，重新开始比对。

3.2 完整代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

// 查找子串，返回起始下标，无则返回-1
int findSubStr(const char str[], const char sub[])
{
    int lenStr = strlen(str);
    int lenSub = strlen(sub);
    
    // 子串为空 或 子串比主串长，直接不存在
    if (lenSub == 0 || lenSub > lenStr)
        return -1;

    // i：主串匹配起始位置，最多走到 lenStr-lenSub
    for (int i = 0; i <= lenStr - lenSub; i++)
    {
        int j = 0;
        // 逐个字符比对子串
        while (str[i + j] == sub[j])
        {
            j++;
            // 子串全部匹配完成，返回起始下标i
            if (j == lenSub)
                return i;
        }
    }
    // 遍历完无匹配
    return -1;
}

int main()
{
    char mainStr[] = "hello world hello c";
    char sub1[] = "hello";
    char sub2[] = "java";
    char sub3[] = "c";

    int pos1 = findSubStr(mainStr, sub1);
    int pos2 = findSubStr(mainStr, sub2);
    int pos3 = findSubStr(mainStr, sub3);

    printf("子串\"%s\"位置：%d\n", sub1, pos1); // 0
    printf("子串\"%s\"位置：%d\n", sub2, pos2); // -1
    printf("子串\"%s\"位置：%d\n", sub3, pos3); // 16
    return 0;
}

3.3 方法优缺点分析

• 优点：逻辑极其直观，代码编写简单，直观。
• 缺点：时间复杂度为 O(N × M)。当主串和子串都很长，且存在大量“部分匹配”的情况时（例如主串 “aaaaaab”，子串 “aaab”），效率极低。

四、方法二：调用库函数 strstr（工程最简写法）

4.1 核心思想

在实际工程项目中，无需重复造轮子。C语言标准库 <string.h> 提供了 strstr 函数，其内部通常经过了高度优化，能直接定位子串。

4.2 完整代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

// 常用封装函数（将指针结果转换为下标）
int findSubStr_lib(const char str[], const char sub[])
{
    char* p = strstr(str, sub);
    if (p == NULL)
        return -1;
    return p - str; // 指针相减得到下标
}

int main()
{
    char str[] = "abcdefabc123";
    char sub[] = "abc123";

    char* res = strstr(str, sub);
    if (res == NULL)
    {
        printf("未找到子串\n");
    }
    else
    {
        // 核心技巧：指针相减得到下标
        int idx = res - str;
        printf("子串起始下标：%d\n", idx); // 6
    }
    return 0;
}

4.3 核心细节解析

• 返回值：strstr 返回的是指向子串首次出现位置的指针，如果未找到则返回 NULL。
• 指针运算：利用 C 语言指针运算的特性，res - str 可以直接得到子串在主串中的偏移量（即下标）。这是指针运算的经典应用场景。

五、方法三：KMP 算法（高效匹配）

5.1 核心思想：拒绝回溯，智能跳转

KMP 算法的核心在于当发生匹配失败时，主串指针 i 不回溯，而是利用模式串（子串）自身的“最长公共前后缀”信息，将子串指针 j 智能跳转到合适的位置继续比对。这个跳转信息被存储在 next 数组中。

5.2 完整代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

// 生成next数组（跳转指南）
void getNext(const char sub[], int next[])
{
    int len = strlen(sub);
    next[0] = -1; // 初始状态
    int i = 0, j = -1;
    while (i < len - 1)
    {
        // j == -1 表示从头开始，或者当前字符匹配成功
        if (j == -1 || sub[i] == sub[j])
        {
            i++; j++;
            next[i] = j; // j的值就是当前子串的最长公共前后缀长度
        }
        else
            j = next[j]; // 匹配失败，回溯j，寻找更短的公共前后缀
    }
}

// KMP查找子串
int kmpFind(const char str[], const char sub[])
{
    int lenS = strlen(str);
    int lenT = strlen(sub);
    if (lenT == 0 || lenT > lenS) return -1;

    int next[100] = { 0 }; // 实际工程中应动态分配或使用模式串长度
    getNext(sub, next);

    int i = 0, j = 0; // i为主串指针，j为模式串指针
    while (i < lenS && j < lenT)
    {
        // j == -1 表示模式串从头开始比对，或者当前字符匹配成功
        if (j == -1 || str[i] == sub[j])
        {
            i++; j++;
        }
        else
            j = next[j]; // 匹配失败，根据next数组调整模式串指针
    }
    // j 走到模式串末尾，说明匹配成功
    if (j == lenT)
        return i - j; // 返回主串中匹配开始的下标
    return -1;
}

int main()
{
    char s[] = "ababcabcabx";
    char t[] = "abcabx";
    printf("KMP匹配下标：%d", kmpFind(s, t)); // 5
    return 0;
}

5.3 核心细节解析

• next数组的推导：next[i] 存储的是子串前 i 个字符组成的子串中，最长相等前后缀的长度。当 sub[i] != sub[j] 时，通过 j = next[j] 不断回溯，直到找到匹配或 j == -1。
• 主串指针不回溯：这是 KMP 算法时间复杂度能达到 O(N + M) 的根本原因。无论子串多长，主串指针 i 始终只增不减。

六、总结与工程实践建议

总结：
暴力匹配法是理解字符串底层操作的基石；strstr 库函数展示了标准库在提升开发效率上的巨大优势；而 KMP 算法则体现了计算机科学中“用空间（next数组）换时间”以及“利用已知信息避免重复计算”的极致优化思想。在实际开发中，日常业务优先使用库函数；若遇到极端的性能瓶颈或算法竞赛，KMP 则是解决长字符串匹配问题的终极武器。