3.1 解决了串"怎么存、基本操作怎么做"。这一节把串真正用起来：先看 C 语言给了哪些现成的串函数，再深入串最经典的问题——模式匹配，从朴素的 $O(n\cdot m)$ 改进到 KMP 的 $O(n+m)$，最后梳理串处理中的常见陷阱，并用"建立词索引表"说明串操作如何组装成真实应用。

学习目标

• 掌握 C 标准串函数 strlen、strcpy、strcat、strcmp、strchr、strrchr 的语义与风险；
• 实现朴素匹配并分析最好、一般、最坏复杂度；
• 理解"失配时主串指针不回退"的约束，由最大长度表推导 next 数组（约定 next[0] = -1），能逐步推演 next 的递推计算，并手工推导任意模式串的 next 与 nextval；
• 论证 KMP 的复杂度为 $O(n+m)$，并说明"主串只扫一遍"的工程价值；
• 识别串处理中的常见陷阱，理解串操作如何组装成词索引表等应用。

C 语言的标准字符串函数库

C 语言没有内置串类型：字符串是"字符数组 + 结束标记"，串值末尾放一个 '\0'（ASCII 中 8 位全 0 的 NULL 符），不计入串长。这种表示下串长是隐含的，求长必须扫描到结束标记——这正是 3.1 讲的串长表示方案中 C 语言的选择。注意这些函数按字节工作，多字节编码下 strlen 返回的是字节数而非字符数（3.1 的"串长≠字节数"）。

<string.h> 提供了一组常用函数，与 3.1 的最小操作子集一一对应：

函数	功能	返回值 / 行为
strlen(s)	求串长	返回 '\0' 之前的字符个数，$O(n)$
strcpy(s1, s2)	串复制	把 s2 复制到 s1，返回 s1；不检查目标容量
strcat(s1, s2)	串拼接	把 s2 接到 s1 末尾；不检查目标容量
strcmp(s1, s2)	串比较	字典序比较，返回 小于0 / 等于0 / 大于0
strchr(s, c)	字符定位	返回 c 首次出现处的指针；找不到返回 NULL
strrchr(s, c)	字符逆定位	返回 c 最后一次出现处的指针；找不到返回 NULL

对照 3.1：strlen ↔ StrLength、strcpy ↔ StrCopy、strcat ↔ Concat、strcmp ↔ StrCompare，而 strchr/strrchr 是"单字符级"的定位，可看作 Index 的特例。例如 s = "The quick brown fox" 中，strchr(s, 'q') 返回指向下标 4 处 'q' 的指针，strrchr(s, 'o') 返回指向最后一次出现 'o' 处的指针。

缓冲区溢出

strcpy、strcat 只知道源串在哪结束，不知道目标数组能装多少，目标空间不够时照样写入，越过数组边界就是缓冲区溢出——C 程序最常见的安全漏洞之一。应改用 strncpy/strncat 并显式传长度，或直接使用能自动管理空间的 std::string。

模式匹配的问题定义

模式匹配：在主串 S（长度为 n，又称目标串）中查找模式串 T（长度为 m，又称模式）首次出现的位置。这是文本编辑器、搜索引擎、信息检索与生物信息学中的基础操作，其效率直接决定这些系统的响应性能。

匹配成功是指找到与模式 T 相等的连续子串，返回该子串首字符在主串中的位置；失败则返回约定值（本文代码返回 -1，也有按 1-based 语义返回 0 的写法）。两个边界约定需要先说清：空模式（$m=0$）视为出现在位置 0；若 $m>n$ 则不可能匹配，直接返回未找到。3.1 用最小操作子集实现的定位函数最坏 $O(n\cdot m)$，本节研究不依赖其他串操作的直接实现，并研究如何从根本上提速。

朴素匹配（Brute Force）

算法思想

朴素匹配的思路非常直观：将模式串与主串中所有可能对齐的起始位置逐一尝试，对每个起始位置，从模式串头部开始逐个字符与主串比对。若所有字符都相等，则匹配成功；若中途某个字符不相等，则放弃当前起始位置，将模式串整体向右移动一位，从新的起始位置重新开始比对。

这个过程的本质就是“暴力枚举”所有可能的对齐起点。

匹配过程示例

先看一个具体例子：设主串 S = "abcababc"，模式串 T = "ababc"。逐趟匹配的过程如下：

趟次（起点）	比较过程	结果
0	a=a, b=b, c≠a	失败（3 次比较）
1	b≠a	失败（1 次）
2	c≠a	失败（1 次）
3	a=a, b=b, a=a, b=b, c=c	成功，位置 3（5 次）

从表中可以直观看到：每一趟都有一个明确的“起始位置”，一旦失配，下一趟就从“起始位置 + 1”重新开始，而模式串指针则回到头部。

双指针与回溯规则

为了实现上述过程，我们使用两个指针：

• i：指向主串 S 中当前正在比较的字符；
• j：指向模式串 T 中当前正在比较的字符。

匹配成功时：S[i] 与 T[j] 相等，说明当前位置对上了。于是 i 和 j 同时往后走一位，继续比较下一个字符。

匹配失败时：S[i] 与 T[j] 不相等，说明当前这一趟尝试失败了。此时需要放弃当前起点，从下一个位置重新开始。

问题是：下一个位置是哪儿？

• 当前趟的起点是 i - j（因为从起点开始，i 和 j 一起走过了 j 个字符，才到达当前位置）；
• 既然这一趟失败了，下一趟就从起点的下一个位置开始，也就是 (i - j) + 1。

所以失配时要做的操作是：

• 把主串指针 i 移到 i - j + 1（回到新起点）；
• 把模式指针 j 归零（从模式串头部重新开始比较）。

写成代码就是：

$$i=i-j+1,j=0$$

C++ 代码实现

基于上述双指针规则，实现代码如下：

int naive_match(std::string_view s, std::string_view p) {
    int n = s.size(), m = p.size();
    int i = 0, j = 0;                       // i 主串指针，j 模式指针
    while (i < n && j < m) {
        if (s[i] == p[j]) { ++i; ++j; }     // 字符相等则双双前进
        else {                              // 失配：主串回到本次起点 + 1，模式归零
            i = i - j + 1;
            j = 0;
        }
    }
    return j == m ? i - m : -1;             // j == m 说明模式全部匹配
}

复杂度分析

最好情况：每趟第 1 个字符就失配，共 $n-m+1$ 次比较（$O(n)$）；或第一趟就整体匹配成功，$m$ 次比较（$O(m)$）。

一般情况：在文本编辑等应用中，模式与主串很少出现长段部分匹配，总比较次数接近 $n+m$。例如在 "A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT" 中查找 "STING"，整个查找只循环 41 次，与 $n+m$ 同阶，因此朴素算法至今仍被采用。

最坏情况：模式与主串之间存在大量"部分匹配"。设模式为 "00000001"（7 个 0 加 1），主串为 52 个 0 后接 1。每趟都成功匹配前 7 个字符、在第 8 个字符处失配，共 46 趟、每趟 8 次比较，即 $46\times 8=368$ 次。一般地：

$$T(n,m)=(n-m+1)\times m=O(n\cdot m).$$

情况	条件	比较次数	复杂度
最好（首字符失配）	模式首字符在主串中几乎不出现	$n-m+1$	$O(n)$
最好（首趟成功）	模式出现在主串开头	$m$	$O(m)$
一般	部分匹配很少	$\approx n+m$	$O(n+m)$
最坏	大量部分匹配后失配	$(n-m+1)\times m$	$O(n\cdot m)$

只含 0、1 两种字符的 01 串特别容易触发最坏情况（图形显示、二进制数据等场景），因为主串中可能存在多个与模式"部分匹配"的子串，引起指针多次回溯。

KMP 的核心思想：失配时主串不回退

从具体例子看问题

观察朴素匹配中最耗时的情况：S = "abababc"，P = "ababc"。

第 0 趟从 S[0] 开始，前 4 个字符 a b a b 都匹配成功，然后在 S[4]='a' 与 P[4]='c' 处失配：

位置:   0 1 2 3 4 5 6
主串:   a b a b a b c
模式:   a b a b c
                ↑
      S[4]='a' 与 P[4]='c' 失配

此时朴素算法会怎么做？把 i 退回 1，j 归零，重新从 S[1] 开始比——但这样浪费了已经比过的信息。

仔细观察已匹配的部分 "abab"，会发现一个关键事实：

• 后缀 "ab"（位置 2~3）与前缀 "ab"（位置 0~1）完全相同。

这意味着什么？既然主串中刚刚匹配完的 "abab" 的后两位 "ab" 已经确认等于模式的 "ab"，而模式的 "ab" 又等于自己的前缀 "ab"，那么主串当前位置前面的 "ab"，实际上已经天然对齐了模式的 "ab" 前缀。

因此，完全没有必要把 i 退回起点！我们只需要：

• 把模式向右滑动 2 位（即 已匹配长度 4 - 前后缀长度 2）；
• 保持主串指针 i 不动（仍然指向 S[4]）；
• 把模式指针 j 从 4 退到 2，用 T[2] 与当前的 S[4] 继续比较。

形式化推导

如果你只想知道 KMP 为什么能工作，上面部分已经足够了。下面这段是写给想看“数学证明”的读者，读不懂可以直接跳过。

当失配发生在 S[i] 与 P[j] 时，假设我们决定用 P[k]（k < j）继续与 S[i] 比较。

要能这么做，必须满足：模式的前 k 个字符能够与主串中 S[i] 前面的 k 个字符对齐，即：

$$P[0..k-1]=S[i-k..i-1]$$

另一方面，因为失配前已经成功匹配了 j 个字符，所以有：

$$P[j-k..j-1]=S[i-k..i-1]$$

这两个等式的右边都是同一段主串子串，因此联立可得：

$$P[0..k-1]=P[j-k..j-1]$$

也就是说，k 必须是模式串自身 P[0..j-1] 的一个相等真前后缀长度。为了让模式滑动得最远、不遗漏任何可能的匹配，应该取满足条件的最大的 k。

这个结论的工程意义极其重大：失配后模式如何滑动，完全由模式串自身预先计算好，与主串无关——这就是 next 数组存在的根本依据。

最大长度表与 next 数组

最大长度表

"最大长度表"把"相等真前后缀"具体化：对模式串从左到右遍历，考察每个前缀 P[0..i]，求它"前缀与后缀的最长公共元素长度"（真前后缀，不含整个串本身）。以经典例子 P = "ABCDABD" 为例：

遍历到	A	AB	ABC	ABCD	ABCDA	ABCDAB	ABCDABD
最长公共元素长度	0	0	0	0	1	2	0

"ABCDAB" 的最大公共长度是 2：前缀 "AB" 与后缀 "AB" 相等，且没有更长的；"ABCDA" 是 1（前缀 "A" = 后缀 "A"）。

从最大长度表到 next 数组

next 数组就是把最大长度表整体向右移动一位、首位置置 -1：

j	0	1	2	3	4	5	6
P[j]	A	B	C	D	A	B	D
最大长度表	0	0	0	0	1	2	0
next[j]	-1	0	0	0	0	1	2

基于这个定义，我们推导失配时“模式串应该向右滑动多少位”。假设匹配过程中，模式串在 P[j] 处与主串失配，这意味着 P[0] 到 P[j-1]（共 j 个字符）已经全部匹配成功了。

1. 借助最大长度表计算滑动位数：
   既然前 j 个字符 P[0..j-1] 已匹配，我们要找出这段子串的“最长相等真前后缀长度”，记这个长度为 L。
   为了不遗漏可能的匹配，模式串应滑动到“已匹配后缀”与“模式前缀”对齐的位置。因此：
   滑动位数 = 已匹配字符数 - L = j - L。

2. 借助 next 数组计算滑动位数：
   根据 next 数组的“右移”定义，next[j] 恰好就等于上面那个“已匹配子串 P[0..j-1]”的最长相等前后缀长度 L。
   因此，滑动位数 = j - next[j]。

举个具体例子

以模式串 P = "ababc" 为例，假设失配发生在 j = 4（即字符 'c' 处失配）。此时前 4 个已匹配字符是 "abab"，它的最长相等真前后缀是 "ab"，长度 L = 2。

计算方法	代入公式	计算过程	滑动位数
最大长度表法	j - L	4 - 2	2 位
next 数组法	j - next[j]	查 next[4] = 2，4 - 2	2 位

可以看到，无论是查最大长度表还是查 next 数组，算出的滑动位数完全一致。前者直观易懂，后者方便编程，两者本质上是在描述同一件事。

三种约定，别混着用

网上能见到 next[0] = -1、next[0] = 0、1-based 等多种版本的 next 数组，表格数值可能整体平移。本教程统一采用 0-based 下标、next[0] = -1。与 1-based 的换算是：1-based 的 next[j] 等于 0-based 的 next[j-1] + 1。例如经典例子 P = "abaabcac"：0-based 为 [-1, 0, 0, 1, 1, 2, 0, 1]，1-based 表为 0 1 1 2 2 3 1 2。实现前务必确认约定，并让匹配代码与之配套。

完整走查：BBC ABCDAB ABCDABCDABDE

以 S = "BBC ABCDAB ABCDABCDABDE"、P = "ABCDABD" 为例完整走一遍：

1. 模式首字符 A 与主串的 B、B、C、空格逐一比较都失配，模式不断右移 1 位，直到与主串第 5 个字符 A 对齐；
2. ABCDAB 六个字符匹配后，D 与主串的空格失配。已匹配子串为 "ABCDAB"，其最长相等真前后缀为 "AB"，长度 L = 2，因此模式右移 $6-2=4$ 位；
3. 对齐后 C 与空格失配。已匹配子串为 "AB"，其最长相等真前后缀长度为 L = 0，因此模式右移 $2-0=2$ 位；
4. 模式首字符 A 与空格失配，右移 1 位；
5. 匹配 ABCDAB 后 D 与 C 失配。已匹配子串仍为 "ABCDAB"，L = 2，再次右移 $6-2=4$ 位；
6. 匹配 ABCDABD 全部成功，过程结束。

整趟走查共 30 次字符比较，而朴素匹配同一输入要 36 次（两趟 ABCDAB 的部分匹配是朴素算法反复回溯的根源）。

手工推导示例

模式 P = "ababc"（0-based，最大长度表为 [0, 0, 1, 2, 0]，next 为 [-1, 0, 0, 1, 2]）：

j	0	1	2	3	4
P[j]	a	b	a	b	c
考察前缀 P[0..j-1]	∅	"a"	"ab"	"aba"	"abab"
最长相等真前后缀	—	无	无	"a"	"ab"
next[j]	-1	0	0	1	2

next[4] = 2 的推导

P[0..3] = "abab"，按候选长度从大到小检查真前后缀：长度为 3 时前缀 "aba"、后缀 "bab"，不等；长度为 2 时前缀 "ab"、后缀 "ab"，相等。因此最长相等真前后缀长度为 2，即 next[4] = 2。失配于 P[4] 时，模式整体右移，直接用 P[2] 与主串当前字符继续比较。

next 数组的递推计算

手工查表只适合短模式，程序里要用递推。build_next 的思路：设进入循环时 k = next[j]，比较 P[j] 与 P[k]——这和匹配时失配回退是同一个模式：

std::vector<int> build_next(std::string_view p) {
    int m = p.size();
    std::vector<int> next(m, 0);
    int k = -1, j = 0;
    next[0] = -1;
    while (j < m - 1) {
        if (k == -1 || p[j] == p[k]) {   // 无候选，或扩展成功
            ++j; ++k;
            next[j] = k;
        } else {
            k = next[k];                 // 回退到更短的候选，与匹配失配同理
        }
    }
    return next;
}

build-next.cpp

两条规则：

1. 若 $p_j=p_k$（或 $k=-1$）：则 P[0..k] 与 P[j-k..j] 相等，最长性保持，所以 next[j+1] = k + 1；
2. 若 $p_j\ne p_k$：把 $k$ 回退为 next[k] 再试。由于 next[k] < k，回退链严格递减必然收敛：最终要么 $p_j$ 与某个 $p_{k^{\prime }}$ 相等得 next[j+1] = k' + 1，要么 $k$ 回到 -1 得 next[j+1] = 0。

用 "ababc" 逐步走查，理解循环如何填出 next = [-1, 0, 0, 1, 2]：

轮次	进入时 j	进入时 k	比较 p[j] 与 p[k]	动作	写下的 next
1	0	-1	—（k == -1，直接扩展）	j←1, k←0	next[1] = 0
2	1	0	b ≠ a	k←next[0] = -1	—
3	1	-1	—（k == -1）	j←2, k←0	next[2] = 0
4	2	0	a = a	j←3, k←1	next[3] = 1
5	3	1	b = b	j←4, k←2	next[4] = 2

第 2、3 轮最能体现"回退"：p[1]='b' 与 p[0]='a' 不等，说明前缀 "ab" 没有非零的真前后缀，于是 k 退回 -1，下一轮从头扩展，得到 next[2] = 0。

构建 next 的时间复杂度为 $O(m)$：k 每次循环最多加 1（共 $m$ 次），沿 next 链回退的总量不超过前进总量，因此总工作量 $O(m)$。

KMP 匹配算法

int kmp_match(std::string_view s, std::string_view p) {
    int n = s.size(), m = p.size();
    if (m == 0) return 0;                   // 约定：空模式视为出现在开头
    std::vector<int> next = build_next(p);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || s[i] == p[j]) { ++i; ++j; }   // 匹配成功，双双前进
        else { j = next[j]; }                        // 失配：模式指针回退，i 不回退
    }
    return j == m ? i - m : -1;
}

kmp-match.cpp

代码讲解：build_next 先用 $O(m)$ 建好 next；匹配循环里 j == -1 表示"模式需要整体右移一格"——此时主串前进一位、模式从 0 重新开始；普通失配只执行 j = next[j]，i 一步都不回退。注意这个回退动作和 build_next 里 k = next[k] 完全同构：都是"利用已经算好的前缀信息，跳到更短的候选再比"。循环结束时 j == m 说明匹配成功，起点是 i - m。

匹配过程示例

S = "abababc"，T = "ababc"，next = [-1, 0, 0, 1, 2]：

步	i	j	动作	累计比较次数
1	0 → 4	0 → 4	a、b、a、b 连续匹配	4
2	4	4	S[4]='a' ≠ T[4]='c'，j ← next[4] = 2	5
3	4 → 7	2 → 5	a、b、c 连续匹配，j == m 成功	8

返回 i - m = 7 - 5 = 2。主串指针 i 从 0 单调走到 7，全程未回退，共 8 次字符比较；朴素算法同输入需要 11 次（第 0 趟 5 次 + 第 1 趟 1 次 + 第 2 趟 5 次）。

复杂度论证

匹配阶段：i 只增不减，最多增加 n 次；j 每次随成功的比较增 1（至多 n 次），而每次失配回退至少减 1，总回退量不超过总前进量。因此匹配阶段的总循环次数是 $O(n)$。

next 构建：k 的前进量不超过 m，回退量不超过前进量，总工作量 $O(m)$。

$$T(n,m)=O(n)+O(m)=O(n+m),S(n,m)=O(m).$$

朴素 vs KMP：常数与场景

前面查 "STING" 的例子中，朴素只比较 41 次，而 KMP 要 68 次——为什么更"高级"的算法反而更慢？因为朴素每次首字符失配只花 1 次比较，KMP 除了同样的字符比较，每次失配还要额外做 next 回退和条件判断；当主串中模式首字符很少出现时，这部分固定开销就成了纯负担。KMP 的优势场景是模式与主串之间存在大量部分匹配，例如 "abababc" 这类输入。

主串只扫一遍：KMP 的工程价值

KMP 最大的特点不是常数意义上的快，而是主串指针单调递增、只需顺序扫描一遍。处理从磁带、网络流或大文件读入的输入时，可以边读边匹配、读过的字节不必重读；朴素算法在主串上反复回退，若输入不能随机访问（磁带要倒带、网络流要重传），回退意味着无法承受的代价。这是 KMP"主串指针不回退"特性真正的工程价值。

nextval：避免必然再次失配的比较

按原始 next 定义，某些失配后的回退比较是必然失败的。例如主串 "aaaabcde"、模式 "aaaaax"，其 next 为 [-1, 0, 1, 2, 3, 4]。若失配发生在 j = 3（即 $s_i{\ne }^{\prime }{a}^{\prime }$），按 next 会依次尝试 p_2、p_1、p_0——它们都是 'a'，必然再次失配，白白比较 3 次。

修正思想：若 $p_j=p_{next[j]}$，则失配于 $p_j$ 时必然也失配于 $p_{next[j]}$，应直接跳到 nextval[next[j]]。由此得到 nextval 的定义：在 next 的基础上，把"与下一位置字符相同"的回退目标继续压缩。

std::vector<int> build_nextval(std::string_view p, const std::vector<int>& next) {
    int m = p.size();
    std::vector<int> nextval(m, 0);
    nextval[0] = -1;
    for (int j = 1; j < m; ++j) {
        int k = next[j];                            // 原定回退位置
        nextval[j] = (p[j] == p[k]) ? nextval[k] : k;
    }
    return nextval;
}

build-nextval.cpp

代码讲解：对每个 j，先取原定回退位置 k = next[j]；若 p[j] 与 p[k] 相同，说明回退到 k 后还会失配，于是直接继承 nextval[k]（可能已经一路压到 -1）；否则保留 k。

模式 "aaaab"：next = [-1, 0, 1, 2, 3] → nextval = [-1, -1, -1, -1, 3]。在 j = 1..3 处失配时直接回到 -1（主串前进），省去全部必然失败的比较；j = 4（p_4 = 'b'）失配时仍回退到 3，因为 'b' ≠ 'a'。0-based 与 1-based 的换算仍按前文约定整体平移，这里不再重复列表。

匹配算法本身不变，只需把 next 换成 nextval；nextval 的构建同样是 $O(m)$。

nextval 什么时候收益明显

模式中存在大量重复字符（如 "aaaa…ab"、"abab…"）时收益明显；字符几乎不重复的模式收益很小。nextval 常被视为 KMP 的标准配置，竞赛与面试中 next 与 nextval 两种写法都常见，关键是讲清约定。

延伸阅读：其他匹配算法

朴素与 KMP 都是单模式、从左到右比较。文本编辑器的"查找"功能常用 BM（Boyer–Moore）算法：模式从右向左比较，失配时利用"坏字符"与"好后缀"规则跳过更多字符，平均性能优于 KMP；AC（Aho–Corasick）算法把 KMP 的"前缀自包含"思想扩展到多模式匹配：一次扫描同时在多个模式串中查找，复杂度 $O(n)$ 且与模式数量无关；Wu-Manber 算法则基于 BM 思想。理解 KMP 的 next 推导，是理解这些算法的基础。本节只引路不展开，后续章节再深入。

串处理中的常见陷阱（字符串的烦恼）

串操作看似简单，工程中却处处是坑，常称之为"字符串的烦恼"。应对它们有一个共同点：先想清楚串的编码、长度、容量与边界，再动手。

• 编码问题：不同系统或平台使用不同编码（ASCII、UTF-8、GBK 等），串跨环境传输时可能出现乱码——基础在 3.1，乱码本质是"同一字节序列被不同编码解读"。
• 匹配与搜索：在大量文本中查找特定字符串或模式可能非常耗时，尤其是正则表达式或模糊匹配——这正是本节模式匹配算法的用武之地。
• 性能问题：连接、分割、替换等操作在大字符串上或大量操作时可能很慢，回顾 3.1 的循环逐字符拼接退化为 $O(k^2)$。
• 边界条件：空字符串、极长字符串、含特殊字符的字符串容易被忽略。例如没处理 m > n 或空模式，就会得到错误结果甚至崩溃。
• 安全性问题：把用户输入直接拼进 SQL 语句会引发 SQL 注入；不检查容量的 strcpy/strcat 会引发缓冲区溢出。
• 多语言支持：中文、emoji、组合字符等复杂字符集与书写规则带来挑战，按字符处理还是按字节处理必须想清楚（3.1 的 UTF-8 字节结构）。

应用举例：建立词索引表

信息检索系统的主要操作是在大量信息中查询特定内容，提高查询效率的关键是建立好的索引。例如图书馆书目检索中，按书名直接检索并不方便，更实用的做法是建立"书名关键词索引"：把书目文件中每本书的书名拆成关键词，按词典序组织成索引表，每个关键词后挂上该书号。

建立过程可概括为三步，反复执行直到文件结束：

1. 从书目文件读入一个书目串；
2. 从书目串中提取所有关键词，插入临时词表——为区分关键词与常用词，需要一张"常用词表"（如 an、a、of、the），凡与常用词相等的单词都不是关键词；
3. 对词表中的每个关键词，在索引表中查找并插入：索引表已有该关键词，就追加一个书号；否则按词典序插入新的索引项。

数据结构按操作特点选择：词表用顺序存储（一本书的关键词数量有限）；索引表常驻、主要供查找使用（后续可用折半查找），宜用顺序存储的有序表，其中关键词用 3.1 的堆分配串以节省存储，而书号索引个数不定、且随生成过程逐个插入，宜用链表。实现上，定位用 StrCompare 找到插入位置、插入用 StrCopy 复制关键词——全部由 3.1 的最小操作子集组合而成。

代价也可以量化：设一本书的书名有 $L$ 个字符、提取出 $k$ 个关键词，索引表已有 $K$ 个索引项。提取关键词 $O(L)$；每个关键词在有序索引表中折半定位 $O(\log K)$，若需插入还要搬移 $O(K)$；书号链表插入 $O(1)$。可见构建成本的大头在"有序插入"，而索引一旦建好，查询就是折半查找 $O(\log K)$——这正是"建索引"与"查索引"的权衡。这个例子说明：串操作很少孤立出现，通常与线性表等结构组装在一起，而"以串的整体为操作对象"（提取、比较、复制整个词）正是串区别于一般线性表的本质。

小结

本节把串从"存"推进到"用"：C 标准串函数库回答了"语言已经给了哪些现成操作"；模式匹配是串最经典的问题——朴素匹配的指针回退暴露了重复比较的浪费，KMP 用最大长度表找出模式自身的相等真前后缀，让主串不回退，把最坏复杂度从 $O(n\cdot m)$ 压到 $O(n+m)$，nextval 再消除必然失配的比较；工程视角下，编码、性能、边界、安全等"字符串的烦恼"决定了一个串程序是否真正可用，词索引表则展示了串操作如何与线性表组装成真实系统。

练习

1. strcpy(s1, s2) 的"不检查容量"意味着什么风险？与 strcat 相比，安全使用要注意什么？
2. 构造一组输入让朴素匹配达到最坏情况，写出比较次数与 n、m 的关系式。
3. 手工推导 P = "ababaa" 的 next 数组（约定 next[0] = -1），并用 build_next 验证。
4. 对 S = "aaaaaaaaab"、P = "aaaab"：朴素匹配与 KMP 各比较多少次？为什么本题中失配总是发生在 j = 4，因而 nextval 没有额外收益？什么输入下 nextval 才能省比较？
5. 在 "A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT" 中查找 "STING"，朴素只比较 41 次而 KMP 要 68 次。为什么？这体现了 KMP 的什么特点？
6. 为什么 next 递推中 k = next[k] 一定收敛？它依赖 next 的什么性质？
7. 若主串只能顺序读一遍（如磁带、网络流输入），KMP 相比朴素算法有什么本质优势？朴素算法在这种情况下还能用吗？
8. （经典练习题）已知模式串 "ADABBADADA"，试求出它对应的 next 函数值和 nextval 函数值。按 1-based 约定 next[1] = 0 求一遍，再换算成 0-based next[0] = -1 的版本。
9. 建立词索引表时为什么需要"常用词表"？索引项中关键词用堆分配串、书号索引用链表，分别基于什么考虑？