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

2026/6/29 2:21:52

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

一、学习目标

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

二、问题拆解与核心逻辑

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

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

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

3.1 核心思路

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

3.2 完整代码实现

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<string.h>// 查找子串，返回起始下标，无则返回-1intfindSubStr(constcharstr[],constcharsub[]){intlenStr=strlen(str);intlenSub=strlen(sub);// 子串为空 或 子串比主串长，直接不存在if(lenSub==0||lenSub>lenStr)return-1;// i：主串匹配起始位置，最多走到 lenStr-lenSubfor(inti=0;i<=lenStr-lenSub;i++){intj=0;// 逐个字符比对子串while(str[i+j]==sub[j]){j++;// 子串全部匹配完成，返回起始下标iif(j==lenSub)returni;}}// 遍历完无匹配return-1;}intmain(){charmainStr[]="hello world hello c";charsub1[]="hello";charsub2[]="java";charsub3[]="c";intpos1=findSubStr(mainStr,sub1);intpos2=findSubStr(mainStr,sub2);intpos3=findSubStr(mainStr,sub3);printf("子串\"%s\"位置：%d\n",sub1,pos1);// 0printf("子串\"%s\"位置：%d\n",sub2,pos2);// -1printf("子串\"%s\"位置：%d\n",sub3,pos3);// 16return0;}

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>// 常用封装函数（将指针结果转换为下标）intfindSubStr_lib(constcharstr[],constcharsub[]){char*p=strstr(str,sub);if(p==NULL)return-1;returnp-str;// 指针相减得到下标}intmain(){charstr[]="abcdefabc123";charsub[]="abc123";char*res=strstr(str,sub);if(res==NULL){printf("未找到子串\n");}else{// 核心技巧：指针相减得到下标intidx=res-str;printf("子串起始下标：%d\n",idx);// 6}return0;}

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数组（跳转指南）voidgetNext(constcharsub[],intnext[]){intlen=strlen(sub);next[0]=-1;// 初始状态inti=0,j=-1;while(i<len-1){// j == -1 表示从头开始，或者当前字符匹配成功if(j==-1||sub[i]==sub[j]){i++;j++;next[i]=j;// j的值就是当前子串的最长公共前后缀长度}elsej=next[j];// 匹配失败，回溯j，寻找更短的公共前后缀}}// KMP查找子串intkmpFind(constcharstr[],constcharsub[]){intlenS=strlen(str);intlenT=strlen(sub);if(lenT==0||lenT>lenS)return-1;intnext[100]={0};// 实际工程中应动态分配或使用模式串长度getNext(sub,next);inti=0,j=0;// i为主串指针，j为模式串指针while(i<lenS&&j<lenT){// j == -1 表示模式串从头开始比对，或者当前字符匹配成功if(j==-1||str[i]==sub[j]){i++;j++;}elsej=next[j];// 匹配失败，根据next数组调整模式串指针}// j 走到模式串末尾，说明匹配成功if(j==lenT)returni-j;// 返回主串中匹配开始的下标return-1;}intmain(){chars[]="ababcabcabx";chart[]="abcabx";printf("KMP匹配下标：%d",kmpFind(s,t));// 5return0;}

5.3 核心细节解析

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

六、总结与工程实践建议

对比维度	暴力匹配法	库函数 strstr	KMP 算法
核心逻辑	双重循环、失败回溯	调用标准库、指针运算	next数组、主串不回溯
时间复杂度	O(N × M)	取决于库实现（通常优化较好）	O(N + M)
代码复杂度	低	极低	高
适用场景	数据量小、理解原理	日常工程开发	算法竞赛、海量文本搜索

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