第 4 章　串（KMP 模式匹配）

4.1　串的定义与存储

4.1.1 基本概念：空串、子串与位置

4.1.2 存储结构：顺序（定长 / 堆分配）与块链

// 定长与堆分配顺序串的类型定义对比

#define MAXLEN 255
typedef struct {          // ① 定长顺序串：空间固定，超长截断
    char ch[MAXLEN];
    int  length;
} SString;
typedef struct {          // ② 堆分配串：运行时按需申请
    char *ch;             // 指向动态分配的存储区
    int  length;
} HString;

4.1.3 串的基本运算：与线性表的差别

4.2　BF 简单模式匹配 方法

4.2.1 算法思想：失配后主串指针回溯

4.2.2 最坏时间复杂度 \(O(nm)\) 及验证

// BF 简单模式匹配：位序从 1 开始，返回 T 在 S 中首次出现的位置，失败返回 0

int BF(char S[], char T[], int n, int m) {
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (S[i] == T[j]) {
            ++i; ++j;              // 当前字符相等，继续比较后继
        } else {
            i = i - j + 2;         // 主串指针回溯到本趟起点的下一位置
            j = 1;                 // 模式串回到第 1 个字符
        }
    }
    if (j > m) return i - m;       // 匹配成功：本趟起点
    else       return 0;           // 匹配失败
}

4.3　KMP 模式匹配 高频考点

4.3.1 next 数组：定义与手算

演示一：\(t=\) 'abaabc'。逐步核对表：

抽查核对：j = 6 时看 'abaab'，头 2 个 'ab' 与尾 2 个 'ab' 相等（长 2），头 3 个 'aba' 与尾 3 个 'aab' 不等，故 next[6] = 2 + 1 = 3 ✓；j = 5 时 'abaa' 头 'a' = 尾 'a'（长 1），头 'ab' ≠ 尾 'aa'，故 next[5] = 2 ✓。

演示二：\(t=\) 'ababaa'。逐步核对表：

抽查核对：j = 6 时 'ababa'，头 'aba' = 尾 'aba'（长 3），故 next[6] = 4 ✓；j = 5 时 'abab'，头 'ab' = 尾 'ab'（长 2），故 next[5] = 3 ✓。

4.3.2 nextval：next 数组的再优化

对上述两串求 nextval（t[next[j]] 一行是比较依据，"—"表示 next[j]=0 无从比较，nextval[1] 恒为 0）：

核对示例：'abaabc' 的 j=3，next[3]=1 且 t[3]='a'=t[1]='a'，故 nextval[3]=nextval[1]=0 ✓；j=4，next[4]=2 且 t[4]='b'=t[2]='b'，故 nextval[4]=nextval[2]=1 ✓。'ababaa' 的 j=6，next[6]=4 但 t[6]='a'≠t[4]='b'，故 nextval[6]=next[6]=4 ✓。

4.3.3 匹配过程演练：主串指针不回溯

主串 \(S=\) 'ababcabcacbab'（\(n=13\)），模式串 \(T=\) 'abcac'（\(m=5\)）。先手算 next：

逐趟匹配（每趟给起点与失配位）：

1. 第 1 趟（起点 1）：\(S_1\)a=\(T_1\) ✓，\(S_2\)b=\(T_2\) ✓，\(S_3\)a≠\(T_3\)c 失配（\(i=3,j=3\)）→ \(j=\mathrm{next}[3]=1\)，\(i\) 不动。本趟 3 次。
2. 第 2 趟（起点 3）：\(S_3\)a ✓，\(S_4\)b ✓，\(S_5\)c ✓，\(S_6\)a ✓（比到 \(T_4\)），\(S_7\)b≠\(T_5\)c 失配（\(i=7,j=5\)）→ \(j=\mathrm{next}[5]=2\)，\(i\) 不动。本趟 5 次。
3. 第 3 趟（起点 6）：\(S_7\)b=\(T_2\) ✓，\(S_8\)c=\(T_3\) ✓，\(S_9\)a=\(T_4\) ✓，\(S_{10}\)c=\(T_5\) ✓ → \(j=6>m\)，成功，位置 \(=i-m=11-5=6\)（\(S[6..10]=\) 'abcac' ✓）。本趟 4 次。

总比较 \(3+5+4=12\) 次 ✓；主串指针 \(i\) 的轨迹 \(1\to2\to\cdots\to11\) 单调前进、从不回退——这正是 KMP 的标志。同一对串 BF 需比较 16 次才成功。

4.3.4 KMP 代码、复杂度与易错点

// 求 next 数组 + KMP 匹配（位序从 1 开始，next[1] = 0）

void get_next(char T[], int next[], int m) {
    int i = 1, j = 0;
    next[1] = 0;                    // 约定
    while (i < m) {
        if (j == 0 || T[i] == T[j]) {
            ++i; ++j;
            next[i] = j;            // t[1..i-1] 最长相等前后缀 + 1
        } else
            j = next[j];            // 前缀指针回退（递推求法）
    }
}

int KMP(char S[], char T[], int next[], int n, int m) {
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || S[i] == T[j]) {
            ++i; ++j;               // 主串指针只前进，从不回溯
        } else
            j = next[j];            // i 不动，模式串右滑
    }
    if (j > m) return i - m;        // 成功：返回起点位序
    else       return 0;
}

4.4　章末自测 真题风格

限时 40 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。所有 next / nextval 手算结果务必逐位核对（用 j=末位抽查一次）。

4.5　本章考点总结