企业官网建设流程全解析

说真的，“串”这一章在很多数据结构教材里都算得上“劝退章”。数组和链表好歹能靠画图硬啃下来，一到了串，除了概念就是匹配算法，朴素匹配还能看得懂，KMP一上来就是next数组、回溯、前缀后缀，直接把新手绕晕。我当年学的时候也一样，书翻了好几遍，代码抄了好几遍，直到自己动手把next数组一步步算出来，才真正明白它到底在干嘛。这篇博客我就按最容易理解的方式，把串是什么、怎么存、怎么匹配、KMP为什么快，一次讲透。你跟着思路走一遍，再自己手算一个例子，基本就稳了。

1. 串到底是个什么东西：先说概念再写代码

1.1 串的本质：它就是一个“受限制的线性表”

串（String）在数据结构里的定义是：由零个或多个字符组成的有限序列。这句话听起来很官方，但拆开看其实特别简单——串本质上就是一个线性表，只不过线性表的元素是整数、结构体，而串的元素是字符。

既然是线性表，那串就有“长度”的概念，有“第一个字符”“最后一个字符”这样的位置关系，也可以用类似线性表的方式去遍历、插入、删除。但它又有自己的特殊性：串的操作对象往往是“串”本身，而不是单个字符，比如查找子串、替换子串、比较两个串的大小，这些操作在工程里太常见了，所以数据结构才会专门把它单独拿出来讲。

举个生活化的例子：你把一串字符想成一条珍珠项链，每个珍珠就是一个字符，项链的长度就是串的长度。你要检查这条项链里有没有某一段特定颜色排列的珠子，那就是“模式匹配”。如果你把项链拆开，从中抽出一小段，那这一小段就叫“子串”。

1.2 主串、子串、模式串：刷题和考试绕不开的三件套

串这一章里，三个概念会反复出现：主串、子串、模式串。

• 主串（S）：被查找的完整字符序列，比如S = "ababcabcacbab"。
• 子串：主串中任意连续的一段，比如"babc"就是主串的一个子串。
• 模式串（P）：你要寻找的目标串，比如你想在S里找P = "abcac"是否存在，P就是模式串。

有些同学会混淆“子串”和“子序列”，这里必须强调一下：子串要求连续，而子序列不要求连续。"aac"是上面S的子序列，但不是子串，因为字符在原串里不是紧挨着的。这个区别在后续学习动态规划和字符串匹配时经常出现，建议一次记住。

还有一个容易忽略的约定：长度为n的串，它的子串个数是n(n+1)/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-m+1)*m)，简化成O(n*m)。

我在实际项目里见过类似的性能问题：日志文件里逐个模板匹配，用朴素匹配跑，数据量一上来就明显卡顿。虽然日志场景下许多匹配会很快失败，但一旦遇到长串且高度相似的场景，复杂度就会迅速放大。

3.3 朴素匹配就一定没用吗？也不是

说朴素匹配“笨”，并不意味着它一无是处。相反，在模式串很短、主串基本随机的情况下，朴素匹配的平均时间复杂度接近O(n+m)，因为第一轮大概率就会失配，根本不需要比较多次。比如在英文文本里找一个普通单词，朴素匹配跑起来很快。

我在做小工具时也会默认先用朴素匹配打底，代码短、逻辑清晰、不易出错。只有确认性能成为瓶颈，才会考虑下面要讲的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 > 1，next[j]等于模式串位置j之前的子串的最长相等前后缀长度加1。

如果听起来绕，可以先用“前缀函数”来理解：对于模式串P，定义一个数组pi，pi[i]表示子串P[0...i]的最长相等真前后缀长度。这个pi数组用代码算起来很直观。然后你再把教材的next和pi对应起来：next[j] = pi[j-2] + 1（当j从1开始计数时）。

4.3 手算Next数组：三步法+实例演示

我用一个经典模式串P = "ababaca"来逐步演示。先直接列出它的前缀函数：

手算时我推荐一个三步法：先写所有前缀，再写所有后缀，最后从最长到最短找相等的那一个。比如算"ababa"的前缀：a, ab, aba, abab；后缀：baba, aba, ba, a；最长相等的是"aba"，长度3。这样画出来，很难算错。

接下来把pi转换成教材里严谨的next数组（模式串下标从1开始）：

对应关系就是：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(m+n)

KMP算法分为两个阶段：求pi数组需要扫描一遍模式串，复杂度为O(m)；匹配过程主串指针不回溯，每个主串字符最多让j回退若干次，但总体来看，j的移动次数受pi数组约束，不会超过n次，所以匹配阶段是O(n)。总复杂度O(m+n)。

为什么朴素匹配不行？因为在最坏情况下，主串指针每次失配后都要回退到新的起点，重新比较已经比较过的字符，导致大量重复劳动。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，但同样有“字符串长度”和“字节数组”的区别，弄清楚你操作的是哪种对象，能少踩很多坑。

最后再分享一个我自己带人时常说的技巧：学KMP不要只看代码，一定要亲手算一遍pi数组。拿一张纸，把模式串每个前缀的前后缀写出来，比如"ababa"的前缀有哪些、后缀有哪些，最长公共部分是哪个，长度是多少，逐个位置填表。这个动作看着笨，但比反复读十遍书都管用。等你算完两三个例子，再看那段while循环，就会觉得它是顺着思路自然写出来的，而不是天书。串这一章没有智商门槛，卡住只是因为缺少一次耐心的手算练习。