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#includestdio.h#includestring.h// 查找子串返回起始下标无则返回-1intfindSubStr(constcharstr[],constcharsub[]){intlenStrstrlen(str);intlenSubstrlen(sub);// 子串为空 或 子串比主串长直接不存在if(lenSub0||lenSublenStr)return-1;// i主串匹配起始位置最多走到 lenStr-lenSubfor(inti0;ilenStr-lenSub;i){intj0;// 逐个字符比对子串while(str[ij]sub[j]){j;// 子串全部匹配完成返回起始下标iif(jlenSub)returni;}}// 遍历完无匹配return-1;}intmain(){charmainStr[]hello world hello c;charsub1[]hello;charsub2[]java;charsub3[]c;intpos1findSubStr(mainStr,sub1);intpos2findSubStr(mainStr,sub2);intpos3findSubStr(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#includestdio.h#includestring.h// 常用封装函数将指针结果转换为下标intfindSubStr_lib(constcharstr[],constcharsub[]){char*pstrstr(str,sub);if(pNULL)return-1;returnp-str;// 指针相减得到下标}intmain(){charstr[]abcdefabc123;charsub[]abc123;char*resstrstr(str,sub);if(resNULL){printf(未找到子串\n);}else{// 核心技巧指针相减得到下标intidxres-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#includestdio.h#includestring.h// 生成next数组跳转指南voidgetNext(constcharsub[],intnext[]){intlenstrlen(sub);next[0]-1;// 初始状态inti0,j-1;while(ilen-1){// j -1 表示从头开始或者当前字符匹配成功if(j-1||sub[i]sub[j]){i;j;next[i]j;// j的值就是当前子串的最长公共前后缀长度}elsejnext[j];// 匹配失败回溯j寻找更短的公共前后缀}}// KMP查找子串intkmpFind(constcharstr[],constcharsub[]){intlenSstrlen(str);intlenTstrlen(sub);if(lenT0||lenTlenS)return-1;intnext[100]{0};// 实际工程中应动态分配或使用模式串长度getNext(sub,next);inti0,j0;// i为主串指针j为模式串指针while(ilenSjlenT){// j -1 表示模式串从头开始比对或者当前字符匹配成功if(j-1||str[i]sub[j]){i;j;}elsejnext[j];// 匹配失败根据next数组调整模式串指针}// j 走到模式串末尾说明匹配成功if(jlenT)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始终只增不减。六、总结与工程实践建议对比维度暴力匹配法库函数 strstrKMP 算法核心逻辑双重循环、失败回溯调用标准库、指针运算next数组、主串不回溯时间复杂度O(N × M)取决于库实现通常优化较好O(N M)代码复杂度低极低高适用场景数据量小、理解原理日常工程开发算法竞赛、海量文本搜索总结暴力匹配法是理解字符串底层操作的基石strstr库函数展示了标准库在提升开发效率上的巨大优势而 KMP 算法则体现了计算机科学中“用空间next数组换时间”以及“利用已知信息避免重复计算”的极致优化思想。在实际开发中日常业务优先使用库函数若遇到极端的性能瓶颈或算法竞赛KMP 则是解决长字符串匹配问题的终极武器。
C语言学习笔记20260628：字符串子串查找的三种解法
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#includestdio.h#includestring.h// 查找子串返回起始下标无则返回-1intfindSubStr(constcharstr[],constcharsub[]){intlenStrstrlen(str);intlenSubstrlen(sub);// 子串为空 或 子串比主串长直接不存在if(lenSub0||lenSublenStr)return-1;// i主串匹配起始位置最多走到 lenStr-lenSubfor(inti0;ilenStr-lenSub;i){intj0;// 逐个字符比对子串while(str[ij]sub[j]){j;// 子串全部匹配完成返回起始下标iif(jlenSub)returni;}}// 遍历完无匹配return-1;}intmain(){charmainStr[]hello world hello c;charsub1[]hello;charsub2[]java;charsub3[]c;intpos1findSubStr(mainStr,sub1);intpos2findSubStr(mainStr,sub2);intpos3findSubStr(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#includestdio.h#includestring.h// 常用封装函数将指针结果转换为下标intfindSubStr_lib(constcharstr[],constcharsub[]){char*pstrstr(str,sub);if(pNULL)return-1;returnp-str;// 指针相减得到下标}intmain(){charstr[]abcdefabc123;charsub[]abc123;char*resstrstr(str,sub);if(resNULL){printf(未找到子串\n);}else{// 核心技巧指针相减得到下标intidxres-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#includestdio.h#includestring.h// 生成next数组跳转指南voidgetNext(constcharsub[],intnext[]){intlenstrlen(sub);next[0]-1;// 初始状态inti0,j-1;while(ilen-1){// j -1 表示从头开始或者当前字符匹配成功if(j-1||sub[i]sub[j]){i;j;next[i]j;// j的值就是当前子串的最长公共前后缀长度}elsejnext[j];// 匹配失败回溯j寻找更短的公共前后缀}}// KMP查找子串intkmpFind(constcharstr[],constcharsub[]){intlenSstrlen(str);intlenTstrlen(sub);if(lenT0||lenTlenS)return-1;intnext[100]{0};// 实际工程中应动态分配或使用模式串长度getNext(sub,next);inti0,j0;// i为主串指针j为模式串指针while(ilenSjlenT){// j -1 表示模式串从头开始比对或者当前字符匹配成功if(j-1||str[i]sub[j]){i;j;}elsejnext[j];// 匹配失败根据next数组调整模式串指针}// j 走到模式串末尾说明匹配成功if(jlenT)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始终只增不减。六、总结与工程实践建议对比维度暴力匹配法库函数 strstrKMP 算法核心逻辑双重循环、失败回溯调用标准库、指针运算next数组、主串不回溯时间复杂度O(N × M)取决于库实现通常优化较好O(N M)代码复杂度低极低高适用场景数据量小、理解原理日常工程开发算法竞赛、海量文本搜索总结暴力匹配法是理解字符串底层操作的基石strstr库函数展示了标准库在提升开发效率上的巨大优势而 KMP 算法则体现了计算机科学中“用空间next数组换时间”以及“利用已知信息避免重复计算”的极致优化思想。在实际开发中日常业务优先使用库函数若遇到极端的性能瓶颈或算法竞赛KMP 则是解决长字符串匹配问题的终极武器。
