数据结构第 4 章：串与数组——KMP 与压缩存储

写于 2026-11-01

这一章有两个明显的重点：串的模式匹配（尤其 KMP）和矩阵的压缩存储。前者是所有字符串算法的起点，后者是"用一维数组表示二维逻辑结构"的经典做法——本质仍然是第 1 章那句话：逻辑结构不变，换一种存储方式。

一、串的定义与存储

串是零个或多个字符组成的有限序列。它本质上是元素为字符的线性表，但操作对象通常是"子串"而不是单个字符，所以有自己的一套操作：求长、串联、求子串、定位（模式匹配）。

三种存储方式：

定长顺序存储：用一个定长数组，超出长度会截断（\0 结尾或在头部记长度）
堆分配存储：运行时 malloc 一块正好够的空间，长度可变，最常用
块链存储：每个结点存若干个字符，最后一个结点可能不满。空间利用率低，实际很少用

二、朴素模式匹配（BF）：为什么慢

在主串 S 中找模式串 T。BF 的思路是暴力对齐：从 S 的第 i 个位置开始，逐字符与 T 比较，失配就 i 后移一位重新从 T 的第 1 个字符比。

最坏情况：S = "aaaa…ab"，T = "aaab"，每次都要比到 T 的最后一个字符才失配，复杂度 O(n×m)。

慢的原因很具体：失配后主串指针要回退，之前已经比较过的信息被完全丢弃、重新比。

三、KMP：用 next 数组记住"已经知道的事"

KMP 的核心思想是：失配时主串指针 i 不回退，只移动模式串。能做到这一点，是因为模式串自身有重复结构——失配位置之前的那段前缀，和后缀存在重合，可以直接把模式串"滑"到重合的位置继续比。

next[j] 的含义：当模式串第 j 个字符与主串失配时，模式串应该跳到哪个位置继续比。等价说法是：T[1..j−1] 的最长相等前后缀的长度 + 1。

求 next 的过程本身就是一个"模式串自己匹配自己"的过程，代码很短但要看懂：

void getNext(char T[], int next[]) {
    int j = 1, k = 0;
    next[1] = 0;
    while (j < T[0]) {                    // T[0] 存长度
        if (k == 0 || T[j] == T[k]) {
            j++; k++; next[j] = k;
        } else {
            k = next[k];                  // 回退到更短的相等前后缀
        }
    }
}

复杂度：求 next 是 O(m)，匹配是 O(n)，总共 O(n+m)。这是 KMP 的全部价值所在。

nextval（优化版）：如果 T[j] == T[next[j]]，那么跳到 next[j] 之后必然还会失配，可以直接再往前跳。所以 nextval[j] = nextval[next[j]]（当两字符相等时），否则等于 next[j]。用 nextval 能减少无意义的比较次数。

记忆要点：next 只看模式串，与主串无关。这是 KMP 能在流式数据上工作的原因，也是它优于 BF 的结构性原因。

四、数组的顺序存储与地址计算

二维数组 A[m][n] 按行优先存储时，元素 A[i][j]（下标从 0 开始）的地址：

LOC(i,j) = LOC(0,0) + (i × n + j) × L

按列优先则是 (j × m + i) × L。这类题只要分清"行优先/列优先"和"下标从 0 还是 1 开始"，套公式即可，但两种约定混用是失分主因。

五、特殊矩阵的压缩存储

思路统一：只存有用的元素，用一个映射公式把二维下标换算成一维下标。

对称矩阵（n×n，a[i][j] = a[j][i]）：只存下三角，共 n(n+1)/2 个元素。按行优先存到一维数组 B，下标从 0 开始：

i ≥ j 时（下三角）：k = i(i−1)/2 + j − 1
i < j 时（上三角）：利用对称性换成 k = j(j−1)/2 + i − 1

三角矩阵：上（下）三角全为常数 c，除存三角区外再多存一个 c，共 n(n+1)/2 + 1 个。

对角矩阵（带状矩阵）：只有主对角线附近若干条带非零，按带状压缩。

六、稀疏矩阵：三元组与十字链表

稀疏矩阵指非零元素极少（一般非零元占比 < 5%）的矩阵。存全部元素是巨大浪费。

三元组表：(行号, 列号, 值) 的线性表，再记录总行数、总列数、非零元个数。节省空间，但丧失随机存取——想取 a[i][j] 要遍历三元组。转置时用"按列序递增"或"快速转置"（先统计每列非零元个数，算出各行起始位置，一次扫描完成）可以把转置从 O(n×t) 降到 O(n+t)。

十字链表：每个非零元结点同时挂在一行链表和一列链表上（right 和 down 两个指针），另有行头指针数组和列头指针数组。适合非零元个数在运算中会变化的场景（如矩阵相加），插入删除不必移动元素。

易错点

KMP 的 next 数组下标从 1 开始时 next[1] = 0，从 0 开始时通常 next[0] = -1，两种写法的数值整体错一位，看题目用哪套。
BF 的最坏复杂度是 O(n×m)，不是 O(n+m)；平均情况接近 O(n+m) 但不能当结论。
对称矩阵压缩公式里的 −1 来自"下标从 0 开始"，若从 1 开始要相应调整。
十字链表解决的问题是"非零元位置会变"，不是"更省空间"——它比三元组表占用更多指针。

这一章在整门课里的位置

串是"元素受限的线性表"，所以本章复习了第 2 章的存储方式对比；数组的地址计算则是第 1 章"顺序存储"性质的直接应用。KMP 的 next 数组在思想上属于第 9 章的算法优化（用已知信息避免重复计算），矩阵压缩则是后面第 6 章邻接矩阵存储的前提——不会压缩存储，就不会理解稀疏图为什么要改用邻接表。

补充：next 数组手算一遍就懂了

以模式串 T = "ababaa"（下标从 1 开始）为例，next 的含义是"第 j 位失配时跳到哪一位"：

j	1	2	3	4	5	6
T[j]	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0	1	0	1	0	4

推导思路：next[j] 等于 T[1..j−1] 的最长相等前后缀长度 + 1。

j=3：前缀串是 "ab"，最长相等前后缀长度 0，所以 next=1
j=5：前缀串是 "abab"，最长相等前后缀是 "ab"（长度 2），所以 next=3
j=6：前缀串是 "ababa"，最长相等前后缀是 "aba"（长度 3），所以 next=4

nextval 的化简规则：若 T[j] == T[next[j]]，说明跳过去之后必然还要再失配一次，可直接继承 nextval[next[j]]，所以 nextval[3]=nextval[1]=0（因为 T[3]='a' 与 T[next[3]]=T[1]='a' 相等）。

手算两三遍这个表的规律，比看十遍代码有用——KMP 难的从来不是代码，是"为什么要跳到这里"。

本篇是《数据结构与算法（93 讲）》第 4 章的知识点摘要。KMP 的完整推导与代码演示见课程页；上一章栈与队列，下一章树与二叉树。