串的定义#

串（String）是由零个或多个字符组成的有限序列，记为：

1
S = 'a₁a₂...aₙ'

其中 n 称为串的长度。串是 线性表 的一种特殊形式——其数据元素被限定为字符。但与线性表的主要操作（增删改查单个元素）不同，串的核心操作是子串定位（模式匹配），这也是串在 408 考研中的核心考点。

基本操作集#

其中 Index 操作就是模式匹配问题——在 408 考研中，算法实现层面的核心考点。两种经典算法是 BF算法 和 KMP 算法。

三种存储结构#

408 考研中串的存储结构较少单独出题，但需注意：

• 定长顺序存储中，串长有两种记录方式：下标 0 位置存长度 或 用 ‘\0’ 标记结尾
• KMP 算法实现中，下标从 0 开始还是从 1 开始会影响 next 数组的值，做题时务必看清题目约定

BF 算法（朴素模式匹配）#

1
主串 S:  a b a b c a b c a c
2
模式 T:  a b c
3
         ↑ 第1次对齐

1
// BF 算法（下标从 1 开始）
2
int BF(char S[], char T[], int n, int m) {
3
    int i = 1, j = 1;
4
    while (i <= n && j <= m) {
5
        if (S[i] == T[j]) {
6
            i++;
7
            j++;
8
        } else {
9
            i = i - j + 2;  // i 回退到本次对齐起点的下一位
10
            j = 1;          // j 归零
11
        }
12
    }
13
    if (j > m) return i - m;
14
    return 0;
15
}

1
第1趟: S: a b a b c ...   匹配到第3个字符失败
2
       T: a b c
3
              ↑ 失败
4
第2趟: S: a b a b c ...   i 回退到2重新开始
5
         T: a b c
6
            ↑ 回退到这里（实际上 b≠a 显然不可能匹配）

KMP 算法的引出动机#

KMP 算法的核心优化思路：

1. 主串指针永不回退：已比较过的字符绝不重新比较
2. 利用 next 数组：通过模式串自身的结构信息（最长相等前后缀），确定失配后模式串的滑动位置
3. 预处理算力换匹配时间：O(m) 的预处理代价换来 O(n) 的匹配效率

详细内容见 KMP 算法。

考研高频考点#

• 空串 vs 空格串的概念辨析（选择题）
• 子串个数计算：n(n+1)/2 + 1（含空串）（选择题）
• BF 算法失配时 i 的回退公式 i = i - j + 2（代码填空）
• BF 算法最坏时间复杂度 O(nm) 及最坏比较次数 (n-m+1) x m（选择题/填空题）
• BF 与 KMP 对比：BF 回溯主串指针，KMP 不回溯（简答题必考）
• 三种存储结构的区别与适用场景（概念题）
• 串的基本操作 Index 的实现方式（概念题）