第四章 串（String）

4.1 串的定义和基本操作

串（String）：由零个或多个字符组成的有限序列。记作 $S='a_1a_2\ldots a_n'$，其中 $n$ 为串长。$n=0$ 时称为空串（用 $\varnothing$ 表示）。

⚠️ 空串 vs 空格串：空串长度为0（无任何字符），空格串 " " 长度为1（包含一个空格字符），二者不同！

子串：串中任意个连续字符组成的子序列。空串是任何串的子串，任何串是自身的子串。

子串位置：子串在主串中第一次出现时第一个字符的位置（位序从1开始）。

串 vs 线性表：

• 串是特殊的线性表——数据对象限定为字符集
• 串的操作对象通常是子串（而非单个元素）——如求子串、模式匹配、串联接等
• 线性表的操作多针对单个元素——如查找、插入、删除某个元素

串的比较：按字典序逐字符比较。字符的大小由其编码值决定（ASCII码、Unicode等）。若所有对应字符相同但长度不同，则较短串更小。

基本操作：

• StrAssign(&T, chars)：赋值（生成串T）
• StrCopy(&T, S)：复制
• StrEmpty(S)：判空
• StrLength(S)：求串长
• ClearString(&S)：清空
• DestroyString(&S)：销毁
• Concat(&T, S1, S2)：串联接
• SubString(&Sub, S, pos, len)：求子串
• StrCompare(S, T)：串比较
• Index(S, T, pos)：定位（模式匹配）

🗣️ 大白话：串就是一串字符，比如 "hello" 就是一个长度为5的串。"ell" 就是 "hello" 的子串。

串的存储结构

1. 定长顺序存储：用固定长度数组存储，有4种方案记录串长：

2. 堆分配存储：用 malloc 动态分配空间，串长不受限

3. 块链存储：用链表存储，每个结点存多个字符（存储密度 = 实际字符数 / 链表总容量）

⚠️ 块链存储操作不方便、存储密度低，实际中很少使用。

4.2 串的模式匹配

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

问题：主串 $S$ 中查找模式串 $T$ 的位置。

思路：从主串第1个字符开始，依次与模式串对齐比较，失败就回溯到主串的下一个位置重新比较。

int Index(SString S, SString T) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++; j++;           // 匹配成功，继续比较后续
        } else {
            i = i - j + 2;     // i回溯
            j = 1;              // j归位
        }
    }
    if (j > T.length) return i - T.length;  // 匹配成功
    else return 0;                           // 匹配失败
}

// BF朴素模式匹配（Java下标从0开始）
int indexBF(String S, String T) {
    int i = 0, j = 0;
    while (i < S.length() && j < T.length()) {
        if (S.charAt(i) == T.charAt(j)) {
            i++; j++;
        } else {
            i = i - j + 1;  // i回溯
            j = 0;           // j归位
        }
    }
    if (j >= T.length()) return i - T.length();  // 匹配成功
    else return -1;                               // 匹配失败
}

时间复杂度：

• 最好情况：$O(m)$（第一次就匹配成功，$m$ 为模式串长度）
• 最坏情况：$O(nm)$（$n$ 为主串长度，$m$ 为模式串长度）
• 最坏情况示例：$S$ = "aaa...aab"，$T$ = "aab" → 每次前 $m-1$ 个字符都匹配，到最后一个才失配
• 实际应用中平均接近 $O(n+m)$（因为自然语言中连续部分匹配的概率很低）

🗣️ 大白话：BF算法就像笨办法找人——你拿着一张照片从人群第一个人开始一个个比对。如果发现"不是"，你就回到下一个人重新开始比对。虽然简单但是慢。

二、KMP算法

核心思想：当发生不匹配时，主串指针 $i$ 不回溯，只让模式串指针 $j$ 回退到一个合适的位置。这个"合适的位置"由 next数组 决定。

next数组的含义：next[j] 表示当模式串第 $j$ 个字符与主串发生不匹配时，模式串需要回退到的位置。也就是模式串 $T[1 \ldots j-1]$ 中最长相等真前后缀的长度加1。

next数组的手工求法：

对模式串的每个位置 $j$，求 $T[1 \ldots j-1]$ 的最长相等真前后缀长度，加1。

例：模式串 $T = "abaabcac"$

📏 规则：next[1] 固定为 0。

【KMP 匹配过程完整手工模拟】

以主串 $S$ = "abaabcac"，模式串 $T$ = "abaabc" 为例，next = [0, 1, 1, 2, 2, 3]。

匹配位置 = $i - T.length = 7 - 6 = 1$。

再举一个需要回退的例子：$S$ = "abaacababc"，$T$ = "ababc"，$\text{next} = [0, 1, 1, 2, 1]$。

💡 手算要诀：

1. 先单独求出 next 数组（对模式串 $T$ 逐位求最长相等真前后缀 + 1）
2. 模拟匹配时，$i$ 永远只增不减，失配时只动 $j$（$j = \text{next}[j]$）
3. 当 $j = 0$ 时，说明模式串第1个字符就不匹配，此时 $i$ 和 $j$ 都加1（开始新一轮比较）
4. 考试中常考比较次数：上例中匹配成功共比较了 13 次

⚠️ 2019年真题：KMP 匹配主串 S 和模式串 T，问比较次数。答案是 10 次——关键是准确执行上述步骤表。

KMP算法代码：

int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++; j++;
        } else {
            j = next[j];   // 模式串向右滑动，i不回溯
        }
    }
    if (j > T.length) return i - T.length;
    else return 0;
}

// KMP算法（Java下标从0开始）
// ⚠️ 考研代码陷阱⚠️：Java/C++代码题目中，字符串和next数组下标通常从0开始（next[0]=-1）。
// 而在考研理论选择题/填空题中，默认下标从1开始（next[1]=0）。
// 两者next值恰好差1。务必看清题目要求！
int indexKMP(String S, String T, int[] next) {
    int i = 0, j = 0;
    while (i < S.length() && j < T.length()) {
        if (j == -1 || S.charAt(i) == T.charAt(j)) {
            i++; j++;
        } else {
            j = next[j];  // 模式串向右滑动，i不回溯
        }
    }
    if (j >= T.length()) return i - T.length();
    else return -1;
}

// 求next数组（Java版，下标从0开始）
int[] getNext(String T) {
    int[] next = new int[T.length()];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < T.length() - 1) {
        if (j == -1 || T.charAt(i) == T.charAt(j)) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

时间复杂度：$O(n+m)$

三、KMP的进一步优化——nextval数组

当 $T[j] = T[next[j]]$ 时，回退后仍然会失配，造成不必要的比较。优化后使用 nextval数组：

nextval 手工求法（先求 next，再优化）：

例：模式串 $T$ = "abaabcac"，next = [0, 1, 1, 2, 2, 3, 1, 2]

💡 手算规则：逐列检查 $T[j]$ 是否等于 $T[\text{next}[j]]$：

• 若不等：$\text{nextval}[j] = \text{next}[j]$（不优化）
• 若相等：$\text{nextval}[j] = \text{nextval}[\text{next}[j]]$（递归取值，因为回退后一定还会失配）
• $\text{nextval}[1]$ 固定为 0

// KMP nextval数组优化（Java版，下标从0开始）
int[] getNextVal(String T) {
    int[] next = getNext(T);
    int[] nextval = new int[T.length()];
    nextval[0] = -1;
    for (int j = 1; j < T.length(); j++) {
        if (T.charAt(j) == T.charAt(next[j]))
            nextval[j] = nextval[next[j]];
        else
            nextval[j] = next[j];
    }
    return nextval;
}

🗣️ 大白话：KMP算法的精髓是"别做无用功"。当你发现不匹配时，你已经知道前面一段是匹配的，所以不用从头来过，只需要利用模式串自身的重复结构"滑动"到合适位置继续比较。

📝 真题剖析

【2015年408真题】 已知字符串 $S$ 为 "abaabaabcabaabc"，模式串 $T$ 为 "abaabc"，采用KMP算法进行匹配，第一次出现"失配"（$S[i] \neq T[j]$）时，$i = j =$（）；

A. 3, 3   B. 5, 5   C. 6, 6   D. 4, 4

解析：

$S$: a b a a b a a b c a b a a b c $T$: a b a a b c

从 $i=1, j=1$ 开始逐字符比对：

• $i=1,j=1$: a=a ✓
• $i=2,j=2$: b=b ✓
• $i=3,j=3$: a=a ✓
• $i=4,j=4$: a=a ✓
• $i=5,j=5$: b=b ✓
• $i=6,j=6$: a≠c ✗ → 第一次失配，$i=6, j=6$

答案选C。

📌 第四章总结