写在前头：串这章看着简单，考起来全是细节。很多人在链表和树上面花了大把时间，结果在字符串上栽了跟头——其实不是不懂操作，而是没把"类型定义""存储结构""运算"这三层关系理清楚。这篇文章就拿串的类型定义、存储结构及其运算当主线，把原理、代码和那些踩过的坑一次讲透。

1. 先搞清楚串到底是个啥东西

1.1 从逻辑结构理解串的定义

串（String）就是零个或多个字符组成的有限序列，一般记作S = "a1a2...an"，其中 S 是串名，n 叫串长。n 等于 0 的时候是空串，记作""。

这个定义看起来比线性表多了个"字符"约束，但恰恰是这个约束，决定了后面所有存储结构的选择逻辑。字符在计算机里本质是整数（ASCII 或 Unicode 编码），所以串可以看作元素类型受限的线性表——但实际操作上完全不是一回事，因为字符串的赋值、比较、拼接、子串提取和模式匹配，都是连续内存操作，直接决定性能瓶颈。

还需要区分三个概念：串、子串和主串。子串是串中任意连续字符组成的子序列，比如"ell"是"hello"的子串，而"hlo"不是，因为不连续。这个"连续"二字，就是后面匹配算法的核心约束之一。

另外还要区分"串变量"和"串常量"。串常量是用双引号括起来的字符序列，比如"123"；串变量则是赋值后的内存对象。这个区别在 C 语言里体现最明显——"123"是静态存储区的 const char*，而你定义的char[] arr = "123";是栈上数组，它们的内存行为和生命周期完全不同。

1.2 串的基本操作到底有哪些

数据结构的"类型定义"不只是给出一组字段，更重要的是确定在这个类型上允许哪些操作。串的 ADT（抽象数据类型）一般包含这些操作：

很多初学者一上来就钻进 KMP 算法里，以为串这章考的就是匹配。实际上大部分考试和面试的基础题，反而集中在接续部分——比如定长顺序存储里 Concat 之后怎么处理"截断"、SubString 的 pos 参数越界怎么报错、Index 的返回位置是从 1 开始还是从 0 开始。这些细节才是区分"会背书"和"真懂"的分水岭。

2. 三种存储结构怎么选：定长、堆分配、块链

2.1 定长顺序存储：简单但自带枷锁

定长顺序存储就是用一段固定长度的字符数组来存放串，C 语言里最直观的结构体长这样：

#define MAXLEN 255 typedef struct { char ch[MAXLEN + 1]; // 多留一个位置放 '\0' 或作下标统一 int length; // 当前串长 } SString;

为什么要MAXLEN + 1？这里有一个历史包袱和一个实用性考量。历史包袱是 C 字符串以'\0'结尾，如果定义一个char ch[MAXLEN]，那么实际能存的字符最多是MAXLEN - 1个，最后一个位置要给结束符。如果不想要'\0'这套逻辑，就多开一个位置、用独立的length字段管理长度，那么实际存储上限就是MAXLEN，下标也从 1 开始更自然——这是教材里传统定义法的思路。

定长存储最大的问题就是长度不可变。你定义 255，就只能存 255 个字符。连接两个串的时候尤其危险：

Status Concat(SString *T, SString S1, SString S2) { int i; if (S1.length + S2.length <= MAXLEN) { // 未截断：完整连接 for (i = 1; i <= S1.length; i++) T->ch[i] = S1.ch[i]; for (i = 1; i <= S2.length; i++) T->ch[S1.length + i] = S2.ch[i]; T->length = S1.length + S2.length; return OK; } else if (S1.length < MAXLEN) { // 截断：S2 只能存一部分 for (i = 1; i <= S1.length; i++) T->ch[i] = S1.ch[i]; for (i = 1; i <= MAXLEN - S1.length; i++) T->ch[S1.length + i] = S2.ch[i]; T->length = MAXLEN; return TRUNCATE; // 返回截断标志 } else { // S1 本身就满了，S2 完全装不下 T->length = 0; return ERROR; } }

这段代码里最容易被忽略的是TRUNCATE这个返回值。很多人的实现里要么直接丢弃这个状态，要么用了一个不恰当的ERROR。实际业务中，串被截断往往是灾难性的——比如拼 SQL、拼文件路径，截断了就是另一条语句。定长存储逐步被淘汰不是因为速度慢，而是这种"半成功半失败"的状态让上层逻辑很难处理。

另外注意下标问题：这里我用ch[i]从 1 开始，是因为length字段本身不包含位置 0。如果你从 0 开始存，那么length和下标的关系是str[length - 1]才是最后一个字符。很多人在写 SubString 时出越界问题，根源就在这里——不同教科书下标习惯不一致。

2.2 堆分配存储：灵活的主流选择

堆分配存储的核心思路是：串的存储空间不再固定死，而是按需用malloc和free动态分配。结构体非常简单：

typedef struct { char *ch; // 指向动态分配的存储区 int length; // 串长 } HString;

关键操作是赋值时的空间管理逻辑。我们拿 StrAssign 举例，完整写出来是这样的：

Status StrAssign(HString *T, const char *chars) { int len = strlen(chars); if (T->ch) free(T->ch); // 先释放旧空间 T->ch = (char *)malloc(len * sizeof(char)); if (!T->ch) return ERROR; // 分配失败 for (int i = 0; i < len; i++) T->ch[i] = chars[i]; T->length = len; return OK; }

最容易被忽略的两点：第一，if (T->ch) free(T->ch);不是可选的，如果没有这个判断和释放，连续两次 StrAssign 就会内存泄漏。第二，这里不拷贝'\0'，因为length已经明确表示了串长，不需要用结束符来判断边界。

这里我给一个从业者的直接建议：代码里一定要先释放旧空间再分配新空间，否则第二次赋值时原来那块内存根本没有指针指向它——这就是经典的内存泄漏场景。面试官问堆分配的优势，不只是"可以存任意长度的串"，还包括"可以反复赋值而不需要预先知道最大长度"，但前提是你要把释放逻辑写对。

和定长存储相比，堆分配的空间效率由实际内容决定，不存在"定义 1KB 但只用了 30 字节"的浪费。但代价是 malloc/free 本身的系统开销，以及那 4 或 8 字节的指针加 4 字节的 length 字段。对中小规模字符串来说完全值得。

2.3 块链存储：空间换时间的边角料

块链存储是链表在串上的应用。每个节点可以存 1~N 个字符，外加一个 next 指针：

#define CHUNKSIZE 4 typedef struct Chunk { char ch[CHUNKSIZE]; // 一块内存存 4 个字符 struct Chunk *next; // 下一块 } Chunk; typedef struct { Chunk *head; // 头指针 Chunk *tail; // 尾指针 int length; // 总串长 } LString;

注意这里同时存了 head 和 tail。为什么要 tail？因为串的很多操作，比如 Concat，需要快速找到链尾。如果没有 tail，连接一个串要遍历整条链 O(n)，有了 tail 就是 O(1)。链表里加尾指针是常见优化，尤其适合"尾部追加频繁"的串操作场景。

还有一个指标叫存储密度：

存储密度 = 数据本身占用的存储量 / 实际分配的存储量

一个节点存 4 个字符、4 字节指针（假设 int 4 字节、char 1 字节），那么存储密度是 4 / (4 + 指针大小)。1 字节字符加 4 字节指针，密度只有 4/(4+4) = 0.5——一半空间都拿来存指针了。CHUNKSIZE 越大密度越高，但插入删除的代价也越大，因为每个节点持有的字符多，操作范围扩大。这是个经典的时间空间取舍。

实际开发中你几乎不会用块链来存字符串，因为 O(n) 的随机访问实在难接受——字符串的核心操作之一是取第 i 个字符，链表只能遍历。但块链的思路在文件系统、大对象存储里有价值：把大数据切块链起来，每块带校验信息，断点续传、随机分块读都有用。所以弄清它，不只是为了考试填空，而是理解分块思想的第一站。

有些教材会说块链还有一个变种：每个节点只存 1 个字符，此时存储密度最低，但操作最灵活。实际上这就是普通的字符链表，基本只能当作业题，没有实用价值。

3. 运算实操落地：从最基本的函数到 KMP

3.1 基本运算的代码实现与边界处理

我在这里统一用堆分配结构体HString展开，因为定长与块链的运算本质相同，区别只在存储访问方式。先看最核心的取子串操作，这是最容易写错的一个：

Status SubString(HString *Sub, HString S, int pos, int len) { if (pos < 1 || pos > S.length || len < 0 || pos + len - 1 > S.length) { return ERROR; } if (Sub->ch) free(Sub->ch); if (len == 0) { // 空子串 Sub->ch = NULL; Sub->length = 0; return OK; } Sub->ch = (char *)malloc(len * sizeof(char)); if (!Sub->ch) return ERROR; for (int i = 0; i < len; i++) { Sub->ch[i] = S.ch[pos - 1 + i]; // pos 是 1 起始，数组是 0 起始 } Sub->length = len; return OK; }

重点是pos + len - 1 > S.length这个条件不是随便写的。举例验证：S 长度为 10，pos=8，len=3，那么要取的是第 8、9、10 个字符，最后一个位置是 10，pos + len - 1 = 8 + 3 - 1 = 10，没越界，合法。如果 pos=9，len=2，9 + 2 - 1 = 10，仍然合法。如果 pos=9，len=3，9 + 3 - 1 = 11 > 10，越界，报错。这个公式用数学语言描述就是：子串在 S 中起始于 pos、长度为 len，最后一个字符下标是 (pos-1) + (len-1) = pos + len - 2（数组 0 起始），转换成串位置（1 起始）就是 pos + len - 1。

这里是对"位置从 1 开始还是从 0 开始"极度敏感的典型场景。如果你把 pos 定义成 0 起始，条件就会变成pos + len > S.length。两种写法都对，错的是混着用。

再来看比较操作 StrCompare。比较规则不是先比长度，而是先比第一个不同的字符，字符小者所在的串小；如果所有对应字符都相同，则长度短者小；如果完全一样，则相等。

这个规则和 C 语言的strcmp完全一致。也就是说，在实现 StrCompare 时，你不需要先判断长度，而是先逐字符比较，遇到不同即返回大小关系，最后用length1 - length2决定：

Status StrCompare(HString S, HString T) { for (int i = 0; i < S.length && i < T.length; i++) { if (S.ch[i] != T.ch[i]) return S.ch[i] - T.ch[i]; } return S.length - T.length; }

这里返回的可以是负数、0 或正数，省去了多余的分类讨论。这个写法也是实际开发里 strcmp 的标准实现思路。

3.2 朴素模式匹配：先从最朴素的思路开始

定位操作 Index，通俗讲就是"找子串"。朴素匹配的思路超级简单：从主串的每个位置出发，依次尝试匹配子串的每个字符，直到完全匹配或主串被遍历完。

int Index(HString S, HString T, int pos) { // pos 是主串中开始匹配的位置，1 起始 if (pos < 1 || pos > S.length) return 0; if (T.length == 0) return 0; // 空串按约定返回 0，表示不存在或不匹配 int i = pos; // 主串当前位置 int j = 1; // 子串当前位置 while (i <= S.length && j <= T.length) { if (S.ch[i - 1] == T.ch[j - 1]) { i++; j++; } else { i = i - j + 2; // 主串回溯到下一个位置 j = 1; // 子串从头开始 } } if (j > T.length) return i - T.length; // 子串匹配成功 return 0; }

最让人懵的就是i = i - j + 2这个回溯公式。我们拆解一下：当某个字符不匹配时，主串当前处于位置 i，而子串已经匹配了 j-1 个字符。这次匹配的起点是i - (j - 1)，为了从下一个位置重新开始尝试，所以新起点应该是i - (j - 1) + 1 = i - j + 2。举个例子，S = "hello"，T = "ll"，第一轮 i=1 时'h' != 'l'，j 从 1 变 1，那么新 i 就是1 - 1 + 2 = 2，从第 2 个字符'e'开始继续。这个公式是朴素匹配里最容易写错的地方，背下来不如理解推导过程。

朴素匹配的时间复杂度是 O(n*m)，n 是主串长度，m 是模式串长度。最坏情况下，比如主串是 "aaaaaaaaab"，模式串是 "aaab"，每次都在最后一个字符失败，整体近乎 O(n*m)。对小型文本足够，但对大文本显然不行。

3.3 KMP 算法：next 数组到底在算什么

KMP 的核心不是优化"匹配过程"，而是优化"失败后主串回溯的距离"。朴素匹配失败时，i 要回退到本次起点的下一个位置；KMP 的改进是让 i 尽量不动，只让 j 回退到某个位置，利用已经匹配过的信息跳过一些必然失败的比较。

next 数组的定义不复杂但极易混淆。标准的定义是：对于模式串 T，next[j]表示当第 j 个字符失配时，j 应该回退到的位置。更本质的说法：next[j]等于 T[1..j-1] 这个子串中，最长的相等前缀后缀的长度加 1。

手动求解 next[1] 到 next[5] 时一般这样处理：

解释一下 next[4] 为什么是 2：T[1..3] = "aba"，它的前缀有 "a"、"ab"，后缀有 "ba"、"a"，最长公共前后缀是 "a"，长度是 1，所以 next[4] = 1 + 1 = 2。next[6] 的来源：T[1..5] = "ababa"，最长公共前后缀是 "aba"，长度是 3，所以 next[6] = 3 + 1 = 4。

有些教材把 next 数组定义为"最长相等前缀后缀的长度"不加 1，也没有那个特殊的 next[1] = 0，于是就出现了两个版本的 next。考试和面试时务必先确认定义，否则直接套算法会差一位。

KMP 匹配的核心代码和朴素匹配的差别只在一行：

int Index_KMP(HString S, HString T, int pos) { int i = pos, j = 1; while (i <= S.length && j <= T.length) { if (j == 0 || S.ch[i - 1] == T.ch[j - 1]) { i++; j++; } else { j = next[j]; // i 不动，j 跳转 } } if (j > T.length) return i - T.length; return 0; }

注意到多了j == 0这个分支：当 next[j] = 0 时，j 被置为 0，下一次循环 j 为 0，此时无法比较 S.ch[i-1] 和 T.ch[-1]，所以必须把 j 加回 1、i 前进一步。这是 KMP 实现里很刁钻的细节。

next 数组的递推求法比手动求解重要得多，因为考试不一定只考 next 求值，还会考"为什么这个递推是对的"。递推代码：

void get_next(HString T, int next[]) { int i = 1, j = 0; next[1] = 0; while (i < T.length) { if (j == 0 || T.ch[i] == T.ch[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } }

这里有个让很多人绕进去的点：T.ch[i] == T.ch[j]中 i 和 j 的含义。i 不是主串下标，而是模式串本次要计算的"扩展位置"，j 是已匹配的前缀长度。如果 T.ch[i] == T.ch[j]，说明前缀可以继续延长一位，于是 next[i+1] = j+1。如果不等，j 回退到 next[j]，继续对比，直到 j 为 0，说明没有公共前后缀，next[i+1] = 1。

nextval 是 next 的优化版，把T.ch[i] == T.ch[next[i]]的情况压缩掉，避免无效跳转。对 "aaaaaaab" 这种重复串，next 数组会退化成和朴素匹配差不多的效果，nextval 才能真正体现 KMP 的优势。注意区分：nextval 的求法是在 next 求出之后再扫一遍，如果 T.ch[i] == T.ch[next[i]]，则 nextval[i] = nextval[next[i]]，否则 nextval[i] = next[i]。

一个实际测试感受：对模式串 "ababaa"，朴素匹配在某些主串上每一步都几乎白走，KMP 能直接利用 next 跳过大量位置。数据量大了之后，这个差距不是常数级别的，而是多项式级别的——O(n*m) 对比 O(n+m)，当 m 和 n 都在十万量级时，朴素匹配基本跑不动。

4. 实战中的坑与排查技巧

4.1 常见问题速查表

我在实际写代码和改别人代码的过程中，总结出串运算里最常出问题的几个点，放在一个表里方便你排查：

4.2 字节、字符与编码的隐藏陷阱

教材里讲串的时候，默认一个字符占一个字节，用 ASCII。现实中这个假设几乎不成立——UTF-8 编码下，中文字符占 3 个字节，emoji 占 4 个字节，"串长"到底以字节计还是以字符计，接口必须明确。

比如 UTF-8 下"中"的长度如果是 3 字节，SubString 按字节截断，可能把一个多字节字符劈成两半，产生非法 UTF-8 序列，显示成乱码。有的语言像 Python 的len()返回字符数，但文件流读取按字节，两者很容易搞混。

处理建议是：如果在存储层用字节计长，所有操作都以字节为单位保持一致性，字符边界问题交给编码层处理。如果要在字符层面操作，需要先把字节流解码成字符数组。不要试图在字节数组里直接数中文字符的个数然后猜边界——那是踩坑的开始。

4.3 我在实际项目中踩过的几个坑

第一个坑是 Concat 拼接动态字符串时的性能问题。循环里反复调用 Concat，每次都重新 malloc、free、拷贝，量一上来就卡顿。后来我改成先计算总长度、一次性分配、两次拷贝，性能提升非常明显。这不是算法的问题，是工程习惯问题。

第二个坑是堆分配里忘记处理T->ch = NULL的情况。有些函数把 ch == NULL 当作"空串"处理，但 S.length 又是 0，看起来没问题。可是当你要对空串做 SubString 时，Sub->ch被 malloc(0) 或者直接赋值 NULL，后续 free 的操作要另外判断。干脆约定：空串的 ch 永远是 NULL，长度永远是 0，所有操作都先查 length。

第三个坑很细节：在读外部配置的时候，字符串是"null"和值为 NULL 不是一回事。前者是一个长度为 4 的串，后者是空指针或空串。很多线上问题都是因为没有区分这两个状态，造成配置文件解析时把"null"当成"没有字段"来处理。建议在数据结构的操作上去安全地处理这类情况，而不只是靠调用方约定。

4.4 几个实操经验分享

自己写串运算，有几个习惯我建议早点养成。

• 下标从 1 开始就全程 1 开始，从 0 开始就全程 0 开始，不要在同一个函数里混用。统一之后，pos、length 和数组下标之间的关系可以用一个公式表达，出错概率直线下降。

• 凡是修改串内容的地方，先确认原来内存是否要释放，再确认新内存分配是否成功。顺序是：分配新空间、检查 NULL、拷贝数据、更新 length、最后释放旧空间。这个顺序能避免"The process was terminated due to a problem"这类崩溃。

• 拿着别人封装好的串库用，也要关注 API 的边界约定。返回值代表什么、下标从几开始、有没有截断行为，这些信息在文档里写得再短也要看完再动工。尤其注意Index这种函数的返回约定，不同库的返回规则差异很大。

• KMP 的 next 数组求法多练几遍。不只是求 next，还要知道 nextval 相比 next 到底优化了什么场景。面试挂在这一块的人很多，不是因为算法难，而是定义版本太多、混淆了概念。动手写代码时，我是先写一个求 next 的辅助函数，再把具体模式串摆到数组里逐步调试，遇到问题打印 i、j 和 next[j] 的值——比瞎猜快得多。

最后分享一个顺手的测试小技巧：自己实现完 Index 或 KMP 之后，不要只测匹配成功的情况。用模式串比主串长的情况测、用空串测、用模式串开头匹配但中段失配的情况测、用多个重叠匹配目标的情况测——比如主串是 "abababa"、模式串是 "aba"，检查返回的位置是 1 而不是 3 或 5 的时候，你就能快速判断匹配逻辑到底是从前往后找第一个，还是有别的行为。这些边界用例才是代码里最容易埋雷的地方。