说真的“串”这一章在很多数据结构教材里都算得上“劝退章”。数组和链表好歹能靠画图硬啃下来一到了串除了概念就是匹配算法朴素匹配还能看得懂KMP一上来就是next数组、回溯、前缀后缀直接把新手绕晕。我当年学的时候也一样书翻了好几遍代码抄了好几遍直到自己动手把next数组一步步算出来才真正明白它到底在干嘛。这篇博客我就按最容易理解的方式把串是什么、怎么存、怎么匹配、KMP为什么快一次讲透。你跟着思路走一遍再自己手算一个例子基本就稳了。1. 串到底是个什么东西先说概念再写代码1.1 串的本质它就是一个“受限制的线性表”串String在数据结构里的定义是由零个或多个字符组成的有限序列。这句话听起来很官方但拆开看其实特别简单——串本质上就是一个线性表只不过线性表的元素是整数、结构体而串的元素是字符。既然是线性表那串就有“长度”的概念有“第一个字符”“最后一个字符”这样的位置关系也可以用类似线性表的方式去遍历、插入、删除。但它又有自己的特殊性串的操作对象往往是“串”本身而不是单个字符比如查找子串、替换子串、比较两个串的大小这些操作在工程里太常见了所以数据结构才会专门把它单独拿出来讲。举个生活化的例子你把一串字符想成一条珍珠项链每个珍珠就是一个字符项链的长度就是串的长度。你要检查这条项链里有没有某一段特定颜色排列的珠子那就是“模式匹配”。如果你把项链拆开从中抽出一小段那这一小段就叫“子串”。1.2 主串、子串、模式串刷题和考试绕不开的三件套串这一章里三个概念会反复出现主串、子串、模式串。主串S被查找的完整字符序列比如S ababcabcacbab。子串主串中任意连续的一段比如babc就是主串的一个子串。模式串P你要寻找的目标串比如你想在S里找P abcac是否存在P就是模式串。有些同学会混淆“子串”和“子序列”这里必须强调一下子串要求连续而子序列不要求连续。aac是上面S的子序列但不是子串因为字符在原串里不是紧挨着的。这个区别在后续学习动态规划和字符串匹配时经常出现建议一次记住。还有一个容易忽略的约定长度为n的串它的子串个数是n(n1)/2 1加的那个1是空串。这个公式在有些选择题里会出现我的建议是不要硬背理解原理即可——从每个位置开始可以截出长度不等的连续段数一数就是那个公式。1.3 空串和空格串一字之差全是坑空串Null String是指长度为0的串里面一个字符都没有在C语言里就是一个。而空格串Blank String是只包含空格的串比如 它的长度是3不是0。这两个概念看起来简单但考试和工程里都容易踩坑。我记得有一次排查别人写的代码他用strlen(str) 0判断“串为空”结果有个用户输入了三个空格程序就直接跳过了正常逻辑最后定位到问题才发现他混淆了空串和空格串。处理用户输入时一般需要先移除首尾空格再判断是否为空这个习惯建议从一开始就养成。2. 串的三种存储结构定长顺序、堆分配、块链串的存储结构和线性表类似有顺序存储和链式存储两大类但具体实现时有几个变体实际工程里最常用的是第二种考试里考得最多的是第一种和第二种下面逐个说。2.1 定长顺序存储最简单但最憋屈定长顺序存储就是用一个固定长度的字符数组来存串。比如#define MAXLEN 255 typedef struct { char ch[MAXLEN]; int length; } SString;这种方式的优点是实现简单随机访问快ch[i]直接下标定位缺点是长度写死了当串的实际长度超过MAXLEN时只能截断没法自动扩容。在真实项目里这种“长度写死”的方案很少直接用因为用户输入是不可控的。但在一些嵌入式环境、协议解析固定字段的场景下定长数组反而有优势——内存可控无动态分配性能稳定。我建议你把它当作“理解串存储的起点”而不是在实际C语言项目里的首选。2.2 堆分配存储干活最常用的方案堆分配存储Heap Allocation的思路是先用一个字符指针指向一块动态分配的内存按需分配、按需扩容。典型的结构是这样的typedef struct { char *ch; int length; } HString;需要存串时用malloc分配length 1的空间长度不够时用realloc扩容。C语言标准库里的string.h提供的很多字符串处理函数本质上也是建立在这种动态分配思想之上的。为什么实际工程里推荐它因为在大多数业务场景里你是无法预知输入字符串最长有多长的。用堆分配你可以根据实际长度动态伸缩配合realloc既不会浪费多余空间也不会因为长度不足而截断数据。注意用堆分配存储串时记得在不再使用串的时候调用free释放内存否则频繁创建串又不释放很容易造成内存泄漏。写字符串处理库时尤其是这样。2.3 块链存储理论上存在实践用得不多的折中方案链式存储串就是把线性表的链表思想搬过来每个结点存若干个字符。但这里有个效率问题如果每个结点只存1个字符那存储密度太低一个字符配上指针内存浪费严重。于是有了块链结构——每个结点存一块字符比如4个或8个字符这样指针开销被摊薄了。块链结构的问题在于串的很多操作比如取子串、插入、删除都需要频繁移动字符链式结构在这类操作上并不占优。加上现代CPU缓存对连续内存更友好顺序存储的局部性要好得多所以实际工程几乎不会用块链来存字符串。考试时你只需要知道“串有链式存储的选项但一般用块链结构来提高存储密度”能画出结构图、说清优缺点即可。真让你写一个字符串处理库我建议直接用堆分配顺序存储。三种存储方式的对比总结如下存储方式空间利用是否支持扩容随机访问适合场景定长顺序可能浪费或截断不支持支持长度可预估的固定场景堆分配顺序按需分配支持支持通用场景工程首选块链存储有指针开销支持不支持了解原理即可实践少用3. 朴素模式匹配思路简单为什么说它“笨”讲完存储就进入串这一章的重头戏——模式匹配。简单说就是问主串里是否存在一段和模式串完全一致的内容。最直接的做法就是朴素匹配也叫暴力匹配。3.1 手写一个朴素匹配代码不到十行朴素匹配的思路特别简单从主串的第一个字符开始逐个和模式串的字符比较如果中途发现不相等就把主串的“起点”往后移动一位再从模式串的第一个字符开始比较。用C语言写出来// T为主串n为主串长度P为模式串m为模式串长度 int naiveSearch(char T[], int n, char P[], int m) { if (m 0) return 0; if (m n) return -1; for (int i 0; i n - m; i) { int j 0; while (j m T[i j] P[j]) { j; } if (j m) { return i; // 返回模式串在主串中首次出现的起始下标 } } return -1; // 没找到 }注意循环的上界是i n - m因为从n - m 1这个位置开始剩余字符已经不够一个模式串的长度了再往后比是必然失败的。这个边界条件容易写错新手经常写成i n然后访问越界或者根本无意义地多做了很多次比较。3.2 复杂度分析最坏情况为什么是O(m*n)朴素匹配的最好情况是主串第一个位置就匹配成功只比较m次。但最坏情况就难看了每次都要比较到模式串的最后一个字符才发现不相等。比如主串aaaaaaaaaaaaaaaaab模式串aaaab每轮比较都会发现前面4个字符都相等最后第5个字符不相等于是前功尽弃回到主串的下一个位置重新比较。这种情况下主串有n - m 1个可能的起点每个起点最多比较m次总复杂度就是O((n-m1)*m)简化成O(n*m)。我在实际项目里见过类似的性能问题日志文件里逐个模板匹配用朴素匹配跑数据量一上来就明显卡顿。虽然日志场景下许多匹配会很快失败但一旦遇到长串且高度相似的场景复杂度就会迅速放大。3.3 朴素匹配就一定没用吗也不是说朴素匹配“笨”并不意味着它一无是处。相反在模式串很短、主串基本随机的情况下朴素匹配的平均时间复杂度接近O(nm)因为第一轮大概率就会失配根本不需要比较多次。比如在英文文本里找一个普通单词朴素匹配跑起来很快。我在做小工具时也会默认先用朴素匹配打底代码短、逻辑清晰、不易出错。只有确认性能成为瓶颈才会考虑下面要讲的KMP算法。这一点很重要明确场景边界比盲目追求高级算法更实际。4. KMP算法核心思想与Next数组详解KMP算法全称是Knuth-Morris-Pratt算法由三位学者同时独立发现。它最核心的贡献是当比较失败时主串的指针不用回退只需要把模式串的指针回退到一个合适的位置继续往后比较。4.1 核心思想失配时让主串指针不回溯回顾朴素匹配的失败场景假设主串是ababcab模式串是abc第一次比较到T[2] a和P[2] c时失败。朴素匹配会把主串的起点从0移到1然后重新开始比较。但你会发现这个回退是“多余”的因为主串的T[1] b已经比较过了你很清楚它是什么。KMP的思路就是利用已经比较过的信息让主串的i指针永远只前进不后退模式串的j指针根据预先计算好的“失效表”跳到一个更合适的位置继续比较。这样匹配过程的总比较次数大幅下降。为了做到这一点需要预先分析模式串自身的结构计算一个next数组也叫回退数组。这个数组是KMP算法的灵魂很多人学KMP卡住就是卡在next数组的计算上。4.2 前缀、后缀和Next数组一次把概念盘明白先定义两个概念前缀除最后一个字符外字符串的所有头部子串。比如aba的前缀有a、ab。后缀除第一个字符外字符串的所有尾部子串。比如aba的后缀有ba、a。这里的“真前缀”“真后缀”是指不包含整个字符串本身的前缀和后缀计算最长相等前后缀时必须排除整个串自身否则任何串都和自己相等没有意义。next数组的常见定义严蔚敏教材版是这样的next[j]表示当模式串第j个字符失配时模式串指针应该回退到的位置。其中next[1] 0对于j 1next[j]等于模式串位置j之前的子串的最长相等前后缀长度加1。如果听起来绕可以先用“前缀函数”来理解对于模式串P定义一个数组pipi[i]表示子串P[0...i]的最长相等真前后缀长度。这个pi数组用代码算起来很直观。然后你再把教材的next和pi对应起来next[j] pi[j-2] 1当j从1开始计数时。4.3 手算Next数组三步法实例演示我用一个经典模式串P ababaca来逐步演示。先直接列出它的前缀函数子串最长相等真前后缀长度pia0ab0aba1前缀a后缀aabab2前缀ab后缀abababa3前缀aba后缀abaababac0ababaca1前缀a后缀a手算时我推荐一个三步法先写所有前缀再写所有后缀最后从最长到最短找相等的那一个。比如算ababa的前缀a, ab, aba, abab后缀baba, aba, ba, a最长相等的是aba长度3。这样画出来很难算错。接下来把pi转换成教材里严谨的next数组模式串下标从1开始位置j字符next[j]1a02b13a14b25a36c47a1对应关系就是next[j] pi[j-2] 1其中pi[-1]和pi[0]特判为0和1。考试和面试手撕代码时我建议直接用前缀函数pi来写因为工程代码里几乎都是用0下标数组next作为“跳转位置”直接用pi[j-1]即可不容易混淆。4.4 代码实现getNext与kmpSearch下面给出一套0起点实现的KMP代码不依赖教材的1起点定义但逻辑等价也是我最常用的版本// 计算前缀函数 pi void getPi(char P[], int m, int pi[]) { int j 0; pi[0] 0; // 单个字符没有真前缀也没有真后缀 for (int i 1; i m; i) { while (j 0 P[i] ! P[j]) { j pi[j - 1]; // 回退寻找更短的前缀 } if (P[i] P[j]) { j; } pi[i] j; } } // KMP匹配返回首次出现位置找不到返回-1 int kmpSearch(char T[], int n, char P[], int m, int pi[]) { if (m 0) return 0; getPi(P, m, pi); int j 0; for (int i 0; i n; i) { while (j 0 T[i] ! P[j]) { j pi[j - 1]; } if (T[i] P[j]) { j; } if (j m) { return i - m 1; } } return -1; }这段代码里的while循环是整个算法的精髓当当前位置字符不匹配时并不是直接让j 0而是利用已经算好的pi数组跳到当前已匹配前缀的最长相同前缀处。可以画个图理解已匹配的部分是P[0..j-1]它失配于T[i]那么希望在P[0..j-1]内找到一个后缀这个后缀同时是P的前缀然后从这个前缀之后继续匹配。5. 完整代码与复杂度对比一次跑通才算懂上一节给出了KMP的核心函数但光看代码还差点意思我建议你把它放进一个完整的可运行程序里自己编译、运行、加打印才能真正体会匹配过程。下面是一个完整示例包含朴素匹配和KMP匹配方便你对比结果。5.1 一个可以直接跑起来的完整示例#include stdio.h #include string.h void getPi(char P[], int m, int pi[]) { int j 0; pi[0] 0; for (int i 1; i m; i) { while (j 0 P[i] ! P[j]) { j pi[j - 1]; } if (P[i] P[j]) { j; } pi[i] j; } } int kmpSearch(char T[], int n, char P[], int m, int pi[]) { if (m 0) return 0; getPi(P, m, pi); int j 0; for (int i 0; i n; i) { while (j 0 T[i] ! P[j]) { j pi[j - 1]; } if (T[i] P[j]) { j; } if (j m) { return i - m 1; } } return -1; } int naiveSearch(char T[], int n, char P[], int m) { if (m 0) return 0; if (m n) return -1; for (int i 0; i n - m; i) { int j 0; while (j m T[i j] P[j]) { j; } if (j m) return i; } return -1; } int main() { char T[] ababcabcacbab; char P[] abcac; int n strlen(T); int m strlen(P); int pi[100] {0}; printf(朴素匹配结果: %d\n, naiveSearch(T, n, P, m)); printf(KMP匹配结果: %d\n, kmpSearch(T, n, P, m, pi)); return 0; }运行后两个函数都应该返回5即模式串在主串中第一次出现的下标。如果你把主串和模式串换成前面提到的T aaaaaaaaaaaaaaaaab、P aaaab可以用一个计数器记录两个算法的比较次数朴素匹配的比较次数会明显多于KMP这就是复杂度的直观体现。5.2 复杂度为什么是O(mn)KMP算法分为两个阶段求pi数组需要扫描一遍模式串复杂度为O(m)匹配过程主串指针不回溯每个主串字符最多让j回退若干次但总体来看j的移动次数受pi数组约束不会超过n次所以匹配阶段是O(n)。总复杂度O(mn)。为什么朴素匹配不行因为在最坏情况下主串指针每次失配后都要回退到新的起点重新比较已经比较过的字符导致大量重复劳动。KMP的本质就是把这个“重复劳动”通过预处理缓存下来让每个字符只比较一次严格说主串字符每个最多被比较常数次。5.3 KMP一定比朴素快吗说说适用边界从理论复杂度看KMP确实比朴素匹配稳定但实际工程中“KMP一定最优”是个误区。当模式串很短、主串内容随机性强时朴素匹配平均性能很好而KMP还需要额外的时间计算pi数组和空间存pi数组综合起来可能并不划算。举个例子我在处理一个配置文件解析功能时需要从文本里找关键字每个关键字平均长度只有4到6个字符文本又比较短当时直接用朴素匹配代码简单、维护方便没有引入KMP的复杂度。KMP的优势场景是在模式串较长、主串规模大、且存在大量重复前缀时比如在基因序列里查找特定片段、在大型日志里匹配带重复结构的模板这时KMP的优势才真正体现出来。6. 常见问题与避坑实录这一章我整理了一些我实际见过的高频问题既有初学时的困惑也有工程里踩过的坑希望你能避开。6.1 Next数组算不对小下标处理必须统一最经典的错误是手算next数组时忘记处理前两个位置的特殊值。很多教材规定next[1] 0有的版本是next[1] 0, next[2] 1代码实现里有的用pi[0] 0有的用pi[0] -1。不管跟随哪种定义写代码前一定先确定好下标起点否则后面所有推导都会乱。我的建议是考试按你指定教材的定义来写工程代码直接用0下标pi前缀函数版本因为它逻辑上更直接也不容易和“第j个位置”搞混。6.2 外层循环里的i写错位置现场容易翻车KMP匹配代码里主循环是for (int i 0; i n; i)主串指针i每次固定前进1这个是不能变的。有些同学会把i写到分支里去或者尝试在while里修改i结果是匹配位置错乱甚至死循环。我在调试时喜欢在循环里打印i和j的实时值确认i是严格递增的。如果发现i在某个位置停了基本就是循环结构写错了。6.3 空串和NULL串边界条件处理容易漏空串长度为0的串的模式匹配在任何主串中都应返回0匹配成功因为空串可以视为出现在任意位置。C语言里strlen() 0但指针本身不是NULL。在调用getPi之前一定要判断m 0直接返回否则pi[0]会越界或产生未定义行为。我还见过一种错误把strlen写进循环条件里比如for (int i 0; i strlen(T); i)导致每循环一次就重新计算一次长度数据量大时性能瞬间崩掉。正确做法是在循环前用变量保存长度。6.4 与字符串库函数混淆的几个坑串的底层是字符数组所以有人会把串操作和C语言字符串函数混着用最常见的就是strcpy、strcmp、strcat。这三个函数处理的是“以\0结尾”的字符串而数据结构里的串有时并不以\0结尾而是用length字段标识长度。如果你把一个不带\0的字符数组传给strlen结果会完全不可控可能导致越界读取。所以在实现自己的串结构时要么统一带上终止符要么统一利用length字段操作不要两种混用。这个习惯在移植到其他语言时也适用——很多动态语言虽然没有显式的\0但同样有“字符串长度”和“字节数组”的区别弄清楚你操作的是哪种对象能少踩很多坑。问题现象可能原因解决思路手算next结果和代码不符教材1起点和代码0起点混用统一用0起点pi前缀函数理解匹配主串很长时程序很慢用了朴素匹配且场景是重复结构换KMP提前算好pi数组返回值总是偏1位下标起点没对齐检查返回位置计算i - m 1空串匹配直接崩溃没有对m0做边界处理调用前先判断并返回字符串函数读取越界串不以\0结尾却用了strlen统一用length字段管理长度最后再分享一个我自己带人时常说的技巧学KMP不要只看代码一定要亲手算一遍pi数组。拿一张纸把模式串每个前缀的前后缀写出来比如ababa的前缀有哪些、后缀有哪些最长公共部分是哪个长度是多少逐个位置填表。这个动作看着笨但比反复读十遍书都管用。等你算完两三个例子再看那段while循环就会觉得它是顺着思路自然写出来的而不是天书。串这一章没有智商门槛卡住只是因为缺少一次耐心的手算练习。