文章摘要

  串（字符串）是零个或多个字符组成的有限序列，是计算机里使用最频繁的数据类型之一。本文梳理串的定义与相关概念（空串、空格串、子串、主串），讲解串的顺序存储与链式存储，并重点、完整地推导模式匹配的两大算法——朴素的 BF 算法与高效的 KMP 算法：手算 next 数组、逐行走查匹配过程、拆解 get_next 代码为什么那样写，让读者彻底看懂 KMP。

本栏系列文章

学透CANFD看这个就行(四): 错误帧、位填充、采样点与通信负荷

其他专栏精品文章

CSDN高赞项目：工程训练竞赛之垃圾分类垃圾桶

前言

  上一篇我们讲了队列（先进先出），这一篇进入一个看似简单、实则大有学问的结构——串。串就是字符串，人人都会用，但串的模式匹配算法却值得细究：BF 为什么慢？KMP 为什么快？next 数组到底怎么求？本文把这两个算法从头到尾讲清楚。

---

一、串的定义

  串是由零个或多个字符组成的有限序列，又叫字符串。 一般记为：

s = "a₁a₂...aₙ"  (n ≥ 0)

其中：
  - s：串名
  - 引号内的字符序列：串值
  - aᵢ：串中的字符
  - n：串的长度，n = 0 时称为空串

---

二、串的相关概念

概念	说明	例子
空串	长度为 0 的串	""
空格串	只包含空格的串	" "
子串	串中任意连续字符组成的子序列	"love" 是 "lover" 的子串
主串	包含子串的串	"lover" 是主串
位置	字符在串中的序号	"love" 中 'l' 的位置是 1

  注意区分：空串 "" 是长度为 0 的串；空格串 " " 长度不为 0，只是内容都是空格。

---

三、串的抽象数据类型（ADT））

ADT 串（String）
Data：
    串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation：
    StrAssign(T, *chars)：      生成一个其值等于字符串常量 chars 的串 T
    StrCopy(T, S)：             把串 S 复制到串 T
    ClearString(S)：            清空串 S
    StringEmpty(S)：            若串 S 为空返回 true，否则返回 false
    StrLength(S)：              返回串 S 的元素个数
    StrCompare(S, T)：          比较串 S 和 T，S>T 返回值>0，S=T 返回值=0，S<T 返回值<0
    Concat(T, S1, S2)：         用 T 返回由 S1 和 S2 联接而成的新串
    SubString(Sub, S, pos, len)：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串
    Index(S, T, pos)：          若主串 S 中存在和串 T 值相同的子串，返回它在主串中第 pos 个字符之后第一次出现的位置
    Replace(S, T, V)：          用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串
    StrInsert(S, pos, T)：      在串 S 的第 pos 个字符之前插入串 T
    StrDelete(S, pos, len)：    删除串 S 第 pos 个字符起长度为 len 的子串

---

四、串的存储结构

1. 顺序存储结构

  为了解决空间浪费问题，把数组想象成一个首尾相接的圆环。环形队列的关键是取模运算：

// 入队
void enqueue(struct point p) {
    if ((tail + 1) % MAX_SIZE == head)
        return;                       // 队列已满
    queue[tail] = p;
    tail = (tail + 1) % MAX_SIZE;
}

// 出队
struct point dequeue(void) {
    if (head == tail)
        return error;                 // 队列为空
    struct point p = queue[head];
    head = (head + 1) % MAX_SIZE;
    return p;
}

  通过 (tail + 1) % MAX_SIZE 和 (head + 1) % MAX_SIZE，指针到达数组末尾后会自动绕回开头，数组就"转"起来了。

用一组地址连续的存储单元存储串的字符序列：

#define MAXSIZE 255     // 最大串长

typedef struct {
    char data[MAXSIZE]; // 存储串的一维数组
    int length;         // 串的当前长度
} SqString;

顺序存储的三种表示方法：

方法	存储方式	优点	缺点
定长顺序存储	固定数组，长度从下标 1 开始	实现简单	长度受限
堆分配存储	动态分配内存（malloc、free）	灵活，长度可变	需要管理内存
块链存储	链表存储	插入删除方便	存储密度低

2. 链式存储结构

用链表存储串，每个结点可以存储一个或多个字符：

#define CHUNKSIZE 4     // 每个结点存储的字符数

typedef struct Chunk {          // 自引用结构体
    char ch[CHUNKSIZE];         // 字符数组
    struct Chunk *next;         // 指向下一个结点
} Chunk;

typedef struct {
    Chunk *head;                // 头指针
    Chunk *tail;                // 尾指针
    int length;                 // 串的长度
} LString;

  链式存储中，每个结点存的字符越多，存储密度越高，但插入删除越麻烦；反之亦然。这就是"块链"要权衡的地方。

---

五、朴素模式匹配（BF 算法）

1. 核心思想：暴力穷举

  模式匹配就是在一个主串 S 中查找子串 T 的位置。BF（Brute Force，暴力/朴素）算法的思路简单到一句话：

  把主串的每个位置都当成"起点"，从头到尾和子串一个字符一个字符地比，比不上了就换个起点重新来。

就像用眼睛在 "goodgoogle" 里找 "google"：

主串 S: g o o d g o o g l e
子串 T: g o o g l e

第 1 次从 S[1] 对齐：
  S: g o o d g o o g l e
  T: g o o g l e
        ↑ 比到第 4 个，S[4]='d' ≠ T[4]='g'，失败

第 2 次从 S[2] 对齐：
  S: g o o d g o o g l e
  T:   g o o g l e
      ↑ S[2]='o' ≠ T[1]='g'，失败
...（每次失败就整体往后挪一格）

第 5 次从 S[5] 对齐：g==g, o==o, o==o, g==g, l==l, e==e → 全部匹配！

第 5 次找到了，返回位置 5。

2. 代码逐行讲

/* 在主串 S 的第 pos 个字符起，查找子串 T，返回位置 */
int Index(SString S, SString T, int pos) {
    int i = pos;    // i 指向主串当前要比较的字符
    int j = 1;      // j 指向子串当前要比较的字符

    while (i <= S[0] && j <= T[0]) {
        if (S[i] == T[j]) {
            i++;    // 当前字符相等：两个指针一起往后走
            j++;
        } else {
            i = i - j + 2;   // 失配：主串回退到"本次起点 + 1"
            j = 1;           // 子串回到开头
        }
    }

    if (j > T[0])
        return i - T[0];     // j 走完了子串 → 匹配成功，返回起点
    else
        return 0;            // i 走完了主串 → 匹配失败
}

几个要点：

• i 和 j 同步往前走：相等时一起 ++，比较 k 个字符后两个指针都前进了 k 步。
• 循环条件 i <= S[0] && j <= T[0]：主串比完了还没成功，或子串比完了（成功），都退出。
• 判断成败：j > T[0] 说明子串每个字符都比过去了（成功）；否则是主串先耗尽（失败）。
• 返回值：匹配成功时起点 = i - T[0]。

3. 关键公式：i = i - j + 2 怎么来的

  假设失配发生在当前的 i、j。在这次尝试里，i 和 j 是同时起步、同步前进的：
  - 本次尝试的起点 = i - (j - 1) = i - j + 1
  - 已成功比对的字符有 j - 1 个
失配后"换个起点重新来"，新起点就是旧起点的下一位：

新起点 = 旧起点 + 1 = (i - j + 1) + 1 = i - j + 2

  所以那句 i = i - j + 2; j = 1; 就是"整体往后挪一格重新对"。

4. 完整走一遍

S = "goodgoogle"，T = "google"，pos = 1：

步	i	j	S[i] vs T[j]	动作
1	1	1	g == g	i→2, j→2
2	2	2	o == o	i→3, j→3
3	3	3	o == o	i→4, j→4
4	4	4	d ≠ g	i=4-4+2=2, j=1
5	2	1	o ≠ g	i=2-1+2=3, j=1
6	3	1	o ≠ g	i=3-1+2=4, j=1
7	4	1	d ≠ g	i=4-1+2=5, j=1
8	5	1	g == g	i→6, j→2
9	6	2	o == o	i→7, j→3
10	7	3	o == o	i→8, j→4
11	8	4	g == g	i→9, j→5
12	9	5	l == l	i→10, j→6
13	10	6	e == e	i→11, j→7
—	—	—	j=7 > T[0]=6	成功，返回 11 - 6 = 5

  结果：T 在 S 中从第 5 位开始出现（S[5..10] = "google"）。注意第 4 步失配时，i 从 4 退回了 2 —— 这就是"主串回退"，也是 BF 慢的根源。

5. 复杂度

• 最好情况：一上来就匹配，或每次第一个字符就对不上，主串走一遍就完事，O(n)。
• 最坏情况：S = "aaaaab"、T = "aaab" 这种，每次都比到最后一位才失配，i 反复回退。每轮比 m 个字符、共比 n-m+1 轮，O(n×m)。

  BF 的代价是：每次失配都把已经比较过的信息全扔了——i 无情回退、j 归 1，主串同一段字符被反复比较。这正是 KMP 要解决的问题。

---

六、KMP 模式匹配算法

1. 从 BF 到 KMP：主串不用回退

  还是那个例子：S = "abababac"，T = "ababac"。BF 匹配到第 6 位失配：

S:  a b a b a b a c
T:  a b a b a c
              ↑
    前 5 个 "ababa" 都对上了，第 6 个 b ≠ c，失配

  BF 的做法是 i = i - j + 2，把 i 退回 2 重头再比。但我们已经知道 S[1..5] 等于 "ababa"，而这个串自己内部藏着重复——前 3 个字符 "aba" 和最后 3 个字符 "aba" 一模一样：

"ababa"
 └┬┘ └┬┘
  前3  后3   ← 都是 "aba"

  既然 "ababa" 的后 3 个 "aba" 已经和主串对上、又恰好等于子串自己的前 3 个 "aba"，那这 3 个字符根本不用再比。直接把子串右滑，让它的前缀 "aba" 对齐主串那段 "aba"，接着比第 4 位就行：

S:  a b a b a b a c
T:      a b a b a c     ← i 停在 6 不动，j 从 6 跳到 4
        1 2 3 4 5 6

  主串指针 i 一步没退，只把子串指针 j 从 6 改成 4。 这就是 KMP 与 BF 的全部区别。

2. next 数组 = 最长公共前后缀

  "失配后 j 该跳到哪"只由子串 T 决定，可以提前算好存成 next 数组：

next[j] = 当 T[j] 与主串失配时，j 应该回退到的位置。

1 索引约定下：next[j] = (T[1..j-1] 的最长公共前后缀长度) + 1。

  “T[1..j-1]” 就是失配前已经匹配成功的那些字符。手算 T = "ababac"：

j	T[j]	已匹配串 T[1…j-1]	最长公共前后缀	next[j]
1	a	（不存在）	特殊约定	0
2	b	“a”	无	1
3	a	“ab”	无	1
4	b	“aba”	“a”	2
5	a	“abab”	“ab”	3
6	c	“ababa”	“aba”	4

  所以 next = [_, 0, 1, 1, 2, 3, 4]。

三个死记的规律：
  - next[1] = 0：特殊哨兵，表示"连第一个字符都配不上，主串必须前进一位"。
  - next[2] = 1：只有 1 个字符，不可能有公共前后缀。
  - 其余值：就是"已匹配串的前缀和后缀最长能重叠多长 + 1"。
  拿 next[6] = 4 说人话：当 T[6]='c' 失配时，前面已配好的 "ababa" 最长公共前后缀是 "aba"（长 3），所以跳过这 3 个、从第 4 位接着比。

3. 用 next 匹配

/* KMP 匹配 */
int Index_KMP(SString S, SString T, int pos) {
    int i = pos;
    int j = 1;
    int next[255];
    get_next(T, next);

    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            i++;
            j++;
        } else {
            j = next[j];     // 只动 j，不动 i！
        }
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}

S = "abababac"，T = "ababac"，next = [_,0,1,1,2,3,4]：

步	i	j	S[i] vs T[j]	动作
1	1	1	a == a	i→2, j→2
2	2	2	b == b	i→3, j→3
3	3	3	a == a	i→4, j→4
4	4	4	b == b	i→5, j→5
5	5	5	a == a	i→6, j→6
6	6	6	b ≠ c	j = next[6] = 4，i 停在 6
7	6	4	b == b	i→7, j→5
8	7	5	a == a	i→8, j→6
9	8	6	c == c	i→9, j→7
—	—	—	j=7 > T[0]=6	成功，返回 9 - 6 = 3

  T 在 S 中从第 3 位出现（S[3..8] = "ababac"，没错）。
对比第 6 步：BF 会把 i 退回 2 重头再来；KMP 只把 j 从 6 改到 4，i 纹丝不动。全程 i 从 1 走到 9，主串每个字符最多比较一次。

4. get_next 代码为什么这么写（难点）

/* 计算 next 数组 */
void get_next(SString T, int *next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];     // 关键！
        }
    }
}

  最反直觉的是 else 里的 j = next[j]。理解它的钥匙就一句：
  求 next 的过程，本质是"拿 T 的前缀去匹配 T 的后缀"，也就是对 T 自己做一次 KMP。

• i：指向"现在要给谁求 next"（后缀的末尾）
• j：当前已经匹配上的前缀长度
• T[i] == T[j]：后缀又成功延长一位 → j++，next[i] = j
• T[i] != T[j]：延长失败 → j 不能归零，而是回退到 next[j]，找一个更短、仍可能匹配的前缀
• j == 0：连第一个字符都配不上 → 没有公共前后缀，next[i] = 1

手动推一遍 T = "ababac"，看 j 怎么"退了又进"：

循环	当前 i,j	比较	结果
1	i=1,j=0	j==0	i=2,j=1，next[2]=1
2	i=2,j=1	T[2]=‘b’ ≠ T[1]=‘a’	j=next[1]=0
3	i=2,j=0	j==0	i=3,j=1，next[3]=1
4	i=3,j=1	T[3]=‘a’ == T[1]=‘a’	i=4,j=2，next[4]=2
5	i=4,j=2	T[4]=‘b’ == T[2]=‘b’	i=5,j=3，next[5]=3
6	i=5,j=3	T[5]=‘a’ == T[3]=‘a’	i=6,j=4，next[6]=4

结果 [_,0,1,1,2,3,4]，和手算完全一致。

5. 复杂度

• get_next：i 一路走到底，j 虽会回退，但总的 j++ 次数不超过 i++ 次数 → O(m)。
• 匹配：i 只增不减走一遍主串 → O(n)。

总复杂度 O(n+m)，而 BF 是 O(n×m)。

6. nextval 优化提示

  当 T[j] == T[next[j]] 时（比如 T = "aaaab"），回退过去还是同一个字符、必然再失配，可以把 next 换成 nextval 再"跳一跳"。

---

七、总结

本文把串的核心内容梳理了一遍：
  1. 串的定义：零个或多个字符组成的有限序列，相关概念有空串、空格串、子串、主串、位置。
  2. 顺序存储：三种方式——定长、堆分配、块链；链式存储用块链（每个结点存多个字符）。
  3. BF 算法：暴力穷举，每个起点都试一遍，失配就 i = i - j + 2 整体回退，复杂度 O(n×m)。
  4. KMP 算法：失配后主串指针 i 一步不退，只让 j 按 next 数组（= 最长公共前后缀）回退，复杂度 O(n+m)。
  5. next 数组：next[j] = (T[1..j-1] 最长公共前后缀长度) + 1，求它的过程就是"拿 T 的前缀匹配 T 自己的后缀"。

  串这一章的关键就一句话：模式匹配里，主串能不动就不动，把"回退"交给 next 数组。到这里，线性结构（线性表、栈、队列、串）就全部讲完了，下一篇我们将进入非线性结构的第一站——树。