第二十三章：字符串算法——文本处理的利器¶
你好！欢迎来到第二十三章！在第六章我们已经学习了字符串的基本操作，比如输入输出、拼接、查找等。但在实际应用中，我们经常需要更高效的字符串处理——比如在一篇文章中快速查找某个单词，或者判断两个字符串是否相似。这一章我们将学习一些经典的字符串算法，它们能帮助我们更快、更聪明地处理文本！
23.1 字符串基础回顾¶
在开始新知识前，我们先快速回顾一下 C++ 中字符串的常用操作（主要用 string 类）：
#include <iostream>
#include <string>
using namespace std;
int main() {
string s1 = "hello";
string s2 = "world";
// 拼接
string s3 = s1 + " " + s2; // "hello world"
// 长度
cout << s3.length() << endl; // 11
// 访问字符
cout << s3[0] << endl; // 'h'
// 查找子串
int pos = s3.find("world"); // 返回6
if (pos != string::npos) {
cout << "找到了，位置：" << pos << endl;
}
// 截取子串
string sub = s3.substr(6, 5); // "world"
// 比较
if (s1 == "hello") { ... }
return 0;
}
这些操作底层已经帮我们做了很多工作，但如果我们想要更快的查找（比如在一个很长的文本中找很多个模式串），就需要自己设计算法了。
23.2 字符串匹配——朴素算法¶
问题：给定一个文本串 text 和一个模式串 pattern，判断 pattern 是否在 text 中出现，并返回第一次出现的位置。
最简单直接的方法就是朴素匹配：从文本的每个位置开始，逐一比较字符。
#include <iostream>
#include <string>
using namespace std;
int naiveSearch(const string& text, const string& pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) break;
}
if (j == m) return i; // 完全匹配
}
return -1; // 未找到
}
int main() {
string text = "hello world, this is a simple string.";
string pattern = "world";
int pos = naiveSearch(text, pattern);
if (pos != -1) cout << "找到，位置：" << pos << endl;
else cout << "未找到" << endl;
return 0;
}
时间复杂度：O(n*m)，最坏情况（比如 text = “aaaaaaaaab”, pattern = “aaab”）会很慢。
23.3 KMP算法——更快的匹配¶
KMP算法（Knuth-Morris-Pratt）通过预处理模式串，利用已经匹配过的信息，避免重复比较。它的核心是部分匹配表（next数组），告诉我们当匹配失败时，模式串可以向右滑动多远。
23.3.1 部分匹配表（next数组）¶
next[i] 表示在模式串的 [0, i-1] 子串中，最长的相等前后缀的长度。例如模式串 “ababc” 的 next 数组：
- next[0] = -1（通常定义）
- i=1: “a” 前后缀长度 0
- i=2: “ab” 前后缀无相等 → 0
- i=3: “aba” 前后缀 “a” → 1
- i=4: “abab” 前后缀 “ab” → 2
- i=5: “ababc” 前后缀无 → 0
23.3.2 KMP匹配过程¶
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> buildNext(const string& pattern) {
int m = pattern.length();
vector<int> next(m + 1, 0); // next[j] 表示当第j位失配时，j应该回退到的位置
next[0] = -1;
int i = 0, j = -1;
while (i < m) {
if (j == -1 || pattern[i] == pattern[j]) {
i++; j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
int kmpSearch(const string& text, const string& pattern) {
vector<int> next = buildNext(pattern);
int n = text.length(), m = pattern.length();
int i = 0, j = 0;
while (i < n && j < m) {
if (j == -1 || text[i] == pattern[j]) {
i++; j++;
} else {
j = next[j];
}
}
if (j == m) return i - m;
return -1;
}
int main() {
string text = "ababcabcabababd";
string pattern = "ababd";
int pos = kmpSearch(text, pattern);
cout << "找到位置：" << pos << endl; // 输出10
return 0;
}
KMP算法的时间复杂度是 O(n+m)，比朴素算法快很多。
23.4 字符串哈希——快速比较¶
哈希（Hash）就是把一个字符串映射成一个整数。如果两个字符串的哈希值相等，它们很可能相等。我们可以用哈希在 O(1) 时间内比较两个子串是否相等。
23.4.1 哈希公式¶
常用的方法是把字符串看作一个 base 进制数，并对一个大质数取模（比如 1e9+7）。例如字符串 “abc” 可以计算为：
hash = (a * base^2 + b * base^1 + c * base^0) % MOD
其中 a、b、c 是字符对应的数字（比如 ‘a’ = 1）。
为了快速得到任意子串的哈希，我们可以预处理前缀哈希：
h[i] = (h[i-1] * base + s[i]) % MOD
那么子串 s[l..r] 的哈希为：
hash(l, r) = h[r] - h[l-1] * base^(r-l+1) (可能需要调整取模)
23.4.2 代码实现¶
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int BASE = 131; // 常用基数
const int MOD = 1e9+7;
ULL pow_base[1000005]; // 预计算 base 的幂
void initPow(int n) {
pow_base[0] = 1;
for (int i = 1; i <= n; i++) {
pow_base[i] = pow_base[i-1] * BASE % MOD;
}
}
vector<ULL> buildHash(const string& s) {
int n = s.length();
vector<ULL> h(n+1, 0);
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * BASE + s[i-1]) % MOD;
}
return h;
}
ULL getHash(const vector<ULL>& h, int l, int r) {
// l, r 从0开始，子串 s[l..r]
return (h[r+1] - h[l] * pow_base[r-l+1] % MOD + MOD) % MOD;
}
int main() {
string s = "hello world";
initPow(s.length());
auto h = buildHash(s);
// 比较 "hello" 和 "world" 是否相等
ULL hash1 = getHash(h, 0, 4);
ULL hash2 = getHash(h, 6, 10);
if (hash1 == hash2) cout << "相等" << endl;
else cout << "不相等" << endl;
return 0;
}
23.4.3 应用：快速查找模式串¶
用哈希可以在 O(n) 时间预处理后，O(1) 比较任意子串和模式串的哈希值，从而快速匹配。这种方法简单且实用，不过要注意哈希冲突（可以选两个模数或大质数减少冲突）。
23.5 字典树（Trie）——高效存储和查找¶
字典树（Trie）是一种树形结构，用于高效地存储和查找字符串集合。每个节点代表一个字符，从根到叶子节点的路径就是一个字符串。
23.5.1 基本操作¶
- 插入：从根开始，沿着字符串的字符往下走，如果节点不存在就创建。
- 查找：同样从根开始，如果能完整走完字符串且最后一个节点标记为结束，则存在。
23.5.2 代码实现¶
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 100005; // 假设最多这么多节点
int trie[MAXN][26]; // 每个节点有26个字母的指针
int cnt[MAXN]; // 以该节点结尾的单词个数
int nodeCount = 1; // 根节点编号为0，下一个节点编号从1开始
void insert(const string& word) {
int p = 0;
for (char ch : word) {
int id = ch - 'a';
if (trie[p][id] == 0) {
trie[p][id] = nodeCount++;
}
p = trie[p][id];
}
cnt[p]++; // 标记单词结尾
}
bool search(const string& word) {
int p = 0;
for (char ch : word) {
int id = ch - 'a';
if (trie[p][id] == 0) return false;
p = trie[p][id];
}
return cnt[p] > 0;
}
int main() {
insert("hello");
insert("world");
insert("hi");
cout << search("hello") << endl; // 1
cout << search("hell") << endl; // 0
return 0;
}
23.5.3 应用¶
- 单词自动补全
- 词频统计
- 搜索引擎的词典
23.6 编程实例讲解¶
实例1：重复子串查找¶
题目：给定一个字符串，找出其中最长的不含重复字符的子串长度（滑动窗口+哈希集合）。
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_set<char> window;
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (window.count(s[right])) {
window.erase(s[left]);
left++;
}
window.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
int main() {
string s = "abcabcbb";
cout << "最长无重复子串长度：" << lengthOfLongestSubstring(s) << endl; // 3 ("abc")
return 0;
}
实例2：用Trie统计单词前缀数量¶
// 在Trie节点中增加一个pass统计经过该节点的次数
int pass[MAXN] = {0};
void insert(const string& word) {
int p = 0;
pass[p]++;
for (char ch : word) {
int id = ch - 'a';
if (trie[p][id] == 0) trie[p][id] = nodeCount++;
p = trie[p][id];
pass[p]++;
}
cnt[p]++;
}
int countPrefix(const string& prefix) {
int p = 0;
for (char ch : prefix) {
int id = ch - 'a';
if (trie[p][id] == 0) return 0;
p = trie[p][id];
}
return pass[p]; // 经过该节点的单词数就是以prefix为前缀的单词数
}
23.7 阶段性编程练习¶
- 练习1：用朴素算法和KMP分别实现查找，对比速度。
- 练习2：实现字符串哈希，并解决“字符串中两个子串是否相等”的问题。
- 练习3：用Trie实现一个简单的词典，支持插入和查找。
- 练习4：给定一个字符串，求它的最小循环节（提示：KMP的next数组）。
- 练习5：用哈希判断一个长字符串中有多少个不同的子串（可以枚举所有子串，用set存哈希，但要注意冲突）。
23.8 第23章编程作业¶
作业1：重复的DNA序列¶
给定一个DNA序列（由 A、C、G、T 组成），找出所有出现次数超过一次的长度为10的子串。用哈希或Trie实现。
作业2：单词搜索 II¶
给定一个字符矩阵和一个单词列表，找出所有同时在矩阵和列表中的单词（可以用Trie+DFS）。
作业3：最短回文串¶
给定一个字符串，在它前面添加字符，使其变成回文串，求最短的结果。提示：KMP或哈希。
作业4：字符串编码¶
有一种编码方式：将连续相同的字符替换成该字符加次数，如 “aaabbc” 编码成 “a3b2c1”。实现编码和解码函数。
作业5：敏感词过滤¶
给定一个文本和一系列敏感词，将文本中所有敏感词替换为 ***。要求高效（提示：可以用Trie + AC自动机，选做）。
恭喜你完成了第二十三章的学习！字符串算法在文本处理、搜索引擎、生物信息学等领域有着广泛的应用。掌握了这些工具，你就能更高效地处理各种文本数据。