第8章：字符串（String Algorithms）

一、导读

8.1 本章学习目标

字符串是信息的载体，字符串处理是编程中最基本的技能之一。在算法竞赛中，字符串算法是一个重要而独立的专题，从简单的模式匹配到复杂的后缀数据结构，层层递进，精彩纷呈。

本章的核心学习目标包括：

深入理解 KMP 算法：掌握 next 数组的含义和构造过程，实现 O(n+m) 的字符串匹配。
掌握 Trie（字典树）：理解 Trie 的结构和操作方法，用于高效的前缀查询和字符串统计。
学会字符串哈希：将字符串映射为整数，实现 O(1) 的字符串比较，注意处理哈希冲突。
了解回文串算法：Manacher 算法 O(n) 求最长回文子串。
认识后缀数组：理解后缀数组的概念和构造，用于高级字符串查询。
建立字符串问题的建模能力：将文本处理问题转化为合适的字符串算法模型。

8.2 为什么本章如此重要

字符串算法在竞赛中的出现频率极高，几乎每场比赛都有至少一道字符串相关的题目。从简单的字符串匹配到复杂的多模式匹配，从单个字符串的性质到多个字符串之间的关系，字符串问题的多样性和深度使其成为竞赛的重要考点。

更重要的是，字符串算法在实际应用中有广泛的价值。搜索引擎的文本检索、DNA 序列的比对分析、代码编辑器的文本匹配——这些真实世界的核心功能都依赖于高效的字符串算法。学习本章的内容，不仅是为竞赛做准备，也是为实际工程能力打基础。

KMP 算法是本章的重中之重。它不仅是一个实用的匹配算法，更展示了"利用已知信息避免重复计算"这一重要的算法设计思想。Trie 和字符串哈希则是两个通用工具，在竞赛中频繁出现。

8.3 核心问题引导

在阅读本章时，请带着以下问题思考：

朴素的字符串匹配为什么在最坏情况下是 O(nm)？哪些情况会导致最坏性能？

KMP 的 next 数组到底记录了什么信息？为什么它能避免重复比较？

Trie 相比哈希表存储字符串有什么优势？在什么场景下应该选择 Trie？

字符串哈希的冲突概率如何估算？双哈希为什么更安全？

Manacher 算法是如何利用回文的对称性实现 O(n) 的？

后缀数组的 rank 和 height 数组各有什么用途？

二、核心概念详解

8.1 朴素匹配与 KMP 算法

8.1.1 朴素匹配

最直觉的字符串匹配方法：对文本的每个位置，尝试与模式串逐字符比较：

cpp

int naive_match(const char *s, const char *p) {
    int n = strlen(s), m = strlen(p);
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && s[i + j] == p[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

时间复杂度：最坏 O(nm)。例如 s = "aaaaab"，p = "aaab"，每次匹配到最后一个字符才失败，然后回退重新匹配。

8.1.2 KMP 算法的核心思想

KMP 的关键洞察：当匹配失败时，模式串可以回退到一个更靠前的位置，而不需要从头开始。这个"更靠前的位置"由 next 数组决定。

next 数组的定义：next[i] 表示模式串 p[0..i] 的最长公共前后缀的长度。也就是说，p[0..next[i]-1] 既是 p[0..i] 的前缀，也是它的后缀。

8.1.3 next 数组的构造

cpp

int nxt[1000005];

void get_next(const char *p, int m) {
    nxt[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++) {
        while (j >= 0 && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
}

理解 next 数组：以模式串 "ABABCAB" 为例：

位置:  0 1 2 3 4 5 6
字符:  A B A B C A B
next: -1 -1  0  1 -1  0  1

next[2] = 0：p[0..2] = "ABA"，最长公共前后缀长度为 1（"A"），但这里 next 存的是 j 的值（下标），所以是 0。
next[3] = 1：p[0..3] = "ABAB"，最长公共前后缀是 "AB"，长度为 2，j = 1。

8.1.4 KMP 匹配过程

cpp

void kmp(const char *s, const char *p) {
    int n = strlen(s), m = strlen(p);
    get_next(p, m);
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != p[j + 1]) j = nxt[j];
        if (s[i] == p[j + 1]) j++;
        if (j == m - 1) {
            printf("Found at position %d\n", i - m + 1);
            j = nxt[j];  // 继续查找下一个匹配
        }
    }
}

时间复杂度：构造 next 数组 O(m)，匹配过程 O(n)，总复杂度 O(n + m)。关键在于 j 的总回退次数不超过 j 的总前进次数，因此 while 循环的总执行次数是 O(n)。

8.2 Trie（字典树）

8.2.1 Trie 的结构

Trie 是一种树形数据结构，用于高效存储和检索字符串集合。每条边代表一个字符，从根到某个节点的路径表示一个字符串前缀：

存储 {"he", "her", "hi", "him", "his"}:

        root
       / | \
      h  ... ...
     / \
    e   i
   / \   \
   r  (end) m
  / \       \
(end) ...   (end)

8.2.2 Trie 的实现

cpp

struct Trie {
    int ch[1000005][26], cnt;
    int val[1000005];  // 可选：节点上的值（如词频）
    
    void init() {
        cnt = 0;
        memset(ch[0], 0, sizeof(ch[0]));
        val[0] = 0;
    }
    
    void insert(const char *s) {
        int u = 0;
        for (int i = 0; s[i]; i++) {
            int c = s[i] - 'a';
            if (!ch[u][c]) {
                ch[u][c] = ++cnt;
                memset(ch[cnt], 0, sizeof(ch[cnt]));
                val[cnt] = 0;
            }
            u = ch[u][c];
        }
        val[u]++;  // 标记单词结尾，或统计词频
    }
    
    int search(const char *s) {
        int u = 0;
        for (int i = 0; s[i]; i++) {
            int c = s[i] - 'a';
            if (!ch[u][c]) return 0;
            u = ch[u][c];
        }
        return val[u];
    }
    
    int prefix_count(const char *s) {
        int u = 0;
        for (int i = 0; s[i]; i++) {
            int c = s[i] - 'a';
            if (!ch[u][c]) return 0;
            u = ch[u][c];
        }
        // 统计以 s 为前缀的单词数
        return count_all(u);
    }
    
    int count_all(int u) {
        int res = val[u];
        for (int c = 0; c < 26; c++)
            if (ch[u][c]) res += count_all(ch[u][c]);
        return res;
    }
} trie;

复杂度：插入和查询的时间复杂度都是 O(|s|)，其中 |s| 是字符串长度。空间复杂度为 O(Σ × N)，其中 Σ 是字符集大小，N 是所有字符串的总长度。

8.2.3 Trie 的应用

前缀统计：统计以某个前缀开头的字符串个数
字符串排序：对 Trie 做 DFS，按字典序输出所有字符串
异或最大值：将数字的二进制位插入 Trie，查询与给定数异或结果最大的数

8.3 字符串哈希

8.3.1 基本思想

字符串哈希将字符串映射为一个整数（哈希值），使得不同的字符串大概率有不同的哈希值，从而实现 O(1) 的字符串比较。

最常用的哈希方式是多项式哈希：

hash(s) = s[0] × B^(n-1) + s[1] × B^(n-2) + ... + s[n-1] × B^0  (mod M)

其中 B 是基数（通常取 131 或 13331），M 是大素数（通常取 10⁹+7 或 10⁹+9）。

8.3.2 实现

cpp

typedef unsigned long long ull;
const ull BASE = 131;

ull hash_str(const char *s) {
    ull h = 0;
    for (int i = 0; s[i]; i++)
        h = h * BASE + s[i];
    return h;
}

8.3.3 前缀哈希与子串比较

预处理前缀哈希，可以在 O(1) 时间内比较任意两个子串是否相同：

cpp

const int MAXN = 1000005;
const ull BASE = 131;
ull h[MAXN], p[MAXN];
char s[MAXN];

void init_hash(int n) {
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * BASE + s[i - 1];
        p[i] = p[i - 1] * BASE;
    }
}

// 获取子串 s[l..r] 的哈希值（0-indexed，闭区间）
ull get_hash(int l, int r) {
    return h[r + 1] - h[l] * p[r - l + 1];
}

// 比较 s[l1..r1] 和 s[l2..r2] 是否相同
bool equal(int l1, int r1, int l2, int r2) {
    return get_hash(l1, r1) == get_hash(l2, r2);
}

8.3.4 哈希冲突与双哈希

单一哈希可能被精心构造的数据 hack。使用双哈希（两个不同的 BASE 和 M）可以大幅降低冲突概率：

cpp

const ull BASE1 = 131, BASE2 = 13331;
const ull MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

// 同时维护两组哈希值
ull h1[MAXN], h2[MAXN], p1[MAXN], p2[MAXN];

当两组哈希值都相等时，可以认为两个子串相同，冲突概率降到极低。

8.4 Manacher 算法

8.4.1 问题描述

求一个字符串的最长回文子串。回文串是正读反读相同的字符串。

8.4.2 算法思想

Manacher 算法通过巧妙利用回文的对称性，在 O(n) 时间内求出最长回文子串。

首先对字符串进行预处理，在每个字符之间和两端插入特殊字符 #，统一奇偶长度：

原串: "abaaba"
处理: "#a#b#a#a#b#a#"

这样所有回文串都变成了奇数长度。

cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s[2000005], t[2000005];
int p[2000005];  // p[i] = 以 t[i] 为中心的最长回文半径

void preprocess() {
    int n = strlen(s);
    int k = 0;
    t[k++] = '#';
    for (int i = 0; i < n; i++) {
        t[k++] = s[i];
        t[k++] = '#';
    }
    t[k] = '\0';
}

int manacher() {
    preprocess();
    int n = strlen(t);
    int center = 0, right = 0, max_len = 0;
    
    for (int i = 0; i < n; i++) {
        int mirror = 2 * center - i;
        if (i < right)
            p[i] = min(right - i, p[mirror]);
        else
            p[i] = 0;
        
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t[i - p[i] - 1] == t[i + p[i] + 1])
            p[i]++;
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        max_len = max(max_len, p[i]);
    }
    return max_len;  // 原串中最长回文子串的长度
}

核心优化：利用已知回文的对称性，p[i] 的初始值可以从对称点 p[mirror] 继承，避免了大量重复比较。

8.5 后缀数组简介

8.5.1 概念

后缀数组 sa 是将字符串所有后缀按字典序排序后的结果。sa[i] 表示排名第 i 的后缀的起始位置。

字符串: "banana"
后缀:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

排序后:
5: a        → sa[0] = 5
3: ana      → sa[1] = 3
1: anana    → sa[2] = 1
0: banana   → sa[3] = 0
4: na       → sa[4] = 4
2: nana     → sa[5] = 2

后缀数组是字符串处理的"瑞士军刀"，可以解决模式匹配、最长重复子串、最长公共子串等多种问题。其构造算法（倍增法或 SA-IS）较为复杂，在入门阶段了解概念和应用即可。

三、实战案例

3.1 案例一：前缀统计（Trie 应用）

问题描述：给定 n 个字符串和 m 个查询，每个查询给出一个前缀，求有多少个字符串以该前缀开头。

cpp

#include <cstdio>
#include <cstring>

int ch[1000005][26], cnt, end_cnt[1000005];

void insert(const char *s) {
    int u = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!ch[u][c]) {
            ch[u][c] = ++cnt;
            memset(ch[cnt], 0, sizeof(ch[cnt]));
        }
        u = ch[u][c];
    }
    end_cnt[u]++;
}

int query(const char *s) {
    int u = 0;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!ch[u][c]) return 0;
        u = ch[u][c];
    }
    // DFS 统计子树中所有单词结尾标记之和
    int res = 0;
    // 简化：用 BFS 或递归统计
    // 实际可以在 insert 时维护子树大小
    return end_cnt[u];  // 简化版本
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(ch[0], 0, sizeof(ch[0]));
    memset(end_cnt, 0, sizeof(end_cnt));
    cnt = 0;
    
    char s[1005];
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        insert(s);
    }
    for (int i = 0; i < m; i++) {
        scanf("%s", s);
        printf("%d\n", query(s));
    }
    return 0;
}

3.2 案例二：字符串哈希求不同子串数

问题描述：给定一个字符串，求它有多少个不同的子串。

cpp

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;

typedef unsigned long long ull;
const ull BASE = 131;
char s[1005];
ull h[1005], p[1005];

int main() {
    scanf("%s", s);
    int n = strlen(s);
    
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * BASE + s[i - 1];
        p[i] = p[i - 1] * BASE;
    }
    
    set<ull> hashes;
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            ull hash_val = h[i + len] - h[i] * p[len];
            hashes.insert(hash_val);
        }
    }
    printf("%d\n", (int)hashes.size());
    return 0;
}

3.3 案例三：KMP 求循环节

问题描述：给定一个字符串 s，求它的最短循环节长度。

cpp

#include <cstdio>
#include <cstring>

int nxt[1000005];
char s[1000005];

void get_next(const char *p, int m) {
    nxt[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++) {
        while (j >= 0 && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
}

int main() {
    scanf("%s", s);
    int n = strlen(s);
    get_next(s, n);
    
    int period = n - 1 - nxt[n - 1];
    if (n % period == 0 && period < n)
        printf("最短循环节长度: %d\n", period);
    else
        printf("不存在完整循环节\n");
    return 0;
}

原理：n - 1 - nxt[n-1] 就是最短循环节的长度。如果 n 能被循环节长度整除，说明字符串由该循环节完整重复构成。

四、本章小结

本章系统介绍了字符串算法的核心内容：

KMP 算法：利用 next 数组避免重复比较，O(n+m) 完成字符串匹配。next 数组记录了模式串的最长公共前后缀信息。

Trie 字典树：树形结构存储字符串集合，支持 O(|s|) 的前缀查询和插入。

字符串哈希：将字符串映射为整数，配合前缀哈希实现 O(1) 子串比较。双哈希降低冲突风险。

Manacher 算法：利用回文对称性，O(n) 求最长回文子串。

后缀数组：所有后缀的字典序排列，是高级字符串处理的基石。

字符串算法的精髓在于利用字符串本身的结构信息来避免重复计算。KMP 利用了模式串的自相似性，Manacher 利用了回文的对称性，Trie 利用了前缀的共享性。理解这些共性，才能在面对新的字符串问题时设计出高效的算法。

五、思考与练习

思考题

KMP 的 next 数组和 Z 函数（Z-algorithm）有什么异同？

Trie 的空间复杂度是 O(Σ × N)，如何优化空间使用？（提示：左儿子右兄弟表示法）

字符串哈希中，BASE 和 MOD 的选择对性能有什么影响？为什么 BASE 通常取 131？

后缀数组的 height 数组有什么用途？如何用它求最长重复子串？

编程练习

多模式匹配：给定 n 个模式串和一个文本串，求每个模式串在文本中出现的次数（AC 自动机）。

最长回文子串：用 Manacher 算法实现，并对比中心扩展法的性能。

字符串最小表示法：求一个循环同构串中字典序最小的表示。

最长公共子串：给定两个字符串，求它们的最长公共子串（后缀数组或哈希+二分）。