字符串匹配
字符串匹配是计算机科学中的基础问题，也是算法竞赛中的常见题型。本章将系统介绍多种字符串匹配算法。
问题定义
【定义】字符串匹配问题是指在一个文本串T中查找一个模式串P的所有出现位置。
例如：
- 文本串T = "ABABCABABABC"
- 模式串P = "ABABC"
- P在T中出现的位置是0和7（从0开始计数）
朴素字符串匹配算法(Brute Force)
算法思想
最直接的方法是枚举文本串的每个可能的起始位置，尝试匹配模式串。
代码实现
// 朴素字符串匹配算法
vector<int> naiveStringMatch(string text, string pattern) {
vector<int> positions;
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) {
positions.push_back(i);
}
}
return positions;
}
时间复杂度分析
- 最坏情况：O(n*m)，其中n是文本串的长度，m是模式串的长度。
- 平均情况：对于随机文本，实际上约为O(n+m)。
Rabin-Karp算法
Rabin-Karp算法使用哈希函数来快速比较字符串，减少不必要的字符比较。
算法思想
- 计算模式串的哈希值
- 对文本串中的每个长度为m的子串计算哈希值
- 只有当哈希值匹配时才进行字符比较
代码实现
// Rabin-Karp字符串匹配算法
vector<int> rabinKarp(string text, string pattern) {
vector<int> positions;
int n = text.length();
int m = pattern.length();
// 选择一个较大的质数作为模数，减少哈希冲突
const int prime = 1000000007;
// 选择一个较大的基数，通常使用一个大于字符集大小的数
const int base = 256;
// 计算基数的m-1次方，用于滑动窗口
long long power = 1;
for (int i = 0; i < m - 1; i++) {
power = (power * base) % prime;
}
// 计算模式串的哈希值
long long patternHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * base + pattern[i]) % prime;
}
// 计算文本串第一个窗口的哈希值
long long textHash = 0;
for (int i = 0; i < m; i++) {
textHash = (textHash * base + text[i]) % prime;
}
// 滑动窗口
for (int i = 0; i <= n - m; i++) {
// 哈希值匹配时进行字符比较
if (patternHash == textHash) {
bool match = true;
for (int j = 0; j < m; j++) {
if (text[i+j] != pattern[j]) {
match = false;
break;
}
}
if (match) {
positions.push_back(i);
}
}
// 计算下一个窗口的哈希值
if (i < n - m) {
textHash = ((textHash - text[i] * power) * base + text[i+m]) % prime;
// 处理负数
if (textHash < 0) {
textHash += prime;
}
}
}
return positions;
}
时间复杂度分析
- 平均情况：O(n+m)
- 最坏情况：O(n*m)（当出现大量哈希冲突时）
优缺点
优点：
- 平均情况下效率高
- 可以同时搜索多个模式串
缺点：
- 需要注意哈希冲突
- 实现时需要处理溢出问题
Knuth-Morris-Pratt(KMP)算法
KMP算法通过利用已经匹配的信息，避免不必要的比较，提高匹配效率。
算法思想
- 预处理模式串，计算【部分匹配表】(next数组)
- 在匹配失败时，根据next数组跳过已知不可能匹配的位置
部分匹配表(next数组)
next[i]表示当匹配失败时，模式串应该回退到的位置。它的值是模式串前i个字符的前缀和后缀的最长公共部分长度。
代码实现
// KMP字符串匹配算法
vector<int> KMP(string text, string pattern) {
vector<int> positions;
int n = text.length();
int m = pattern.length();
// 构建next数组
vector<int> next(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j-1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
// 进行匹配
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j-1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
positions.push_back(i - m + 1);
j = next[m-1];
}
}
return positions;
}
next数组的计算解释
- next[0]始终为0，表示模式串的第一个字符匹配失败时，只能重新开始。
- 对于i>0，next[i]是"pattern[0...i-1]"的前缀和后缀的最长公共部分长度。
- 如果pattern[i] = pattern[j]，则next[i] = j+1。
- 如果pattern[i] ≠ pattern[j]，则需要回溯j = next[j-1]，直到找到匹配或j=0。
时间复杂度分析
- 预处理next数组：O(m)
- 匹配过程：O(n)
- 总时间复杂度：O(n+m)
优缺点
优点：
- 最坏情况下也能保证O(n+m)的时间复杂度
- 不需要额外的空间来存储哈希值
缺点：
- 构建next数组较复杂
- 不如Boyer-Moore算法直观
Boyer-Moore算法
Boyer-Moore算法是一种更高效的字符串匹配算法，它通过从右向左扫描模式串来实现更多的跳跃。
算法思想
Boyer-Moore算法基于两个启发式规则：
- 坏字符规则：当不匹配时，根据文本串中的"坏字符"确定跳跃距离
- 好后缀规则：当部分匹配后失败时，根据已匹配的"好后缀"确定跳跃距离
代码实现（简化版，仅使用坏字符规则）
// Boyer-Moore字符串匹配算法（简化版）
vector<int> boyerMoore(string text, string pattern) {
vector<int> positions;
int n = text.length();
int m = pattern.length();
// 处理空串情况
if (m == 0) return positions;
// 构建坏字符表（简化为256个ASCII字符）
vector<int> badChar(256, -1);
for (int i = 0; i < m; i++) {
badChar[(int)pattern[i]] = i;
}
int s = 0; // 模式串在文本串中的起始位置
while (s <= n - m) {
int j = m - 1; // 从模式串的最后一个字符开始匹配
// 从右向左比较
while (j >= 0 && pattern[j] == text[s+j]) {
j--;
}
// 完全匹配
if (j < 0) {
positions.push_back(s);
s++; // 简化处理，实际可以跳过更多
} else {
// 坏字符在模式串中最右出现的位置
int badCharPos = badChar[(int)text[s+j]];
// 根据坏字符规则跳跃
// 注意：如果坏字符不在模式串中，则跳过整个模式长度
// 如果坏字符在j左侧，则右移j-badCharPos位
// 如果坏字符在j右侧，则右移1位（简化处理）
s += max(1, j - badCharPos);
}
}
return positions;
}
时间复杂度分析
- 预处理：O(m + alphabet_size)，其中alphabet_size是字符集大小
- 匹配过程：
- 最坏情况：O(n*m)
- 最优情况：O(n/m)
- 平均情况：O(n)，实际上通常比KMP更快
优缺点
优点：
- 在实践中通常比KMP快
- 特别适合长模式串和大字符集
缺点：
- 完整实现较复杂（需考虑好后缀规则）
- 预处理需要额外空间
Sunday算法
Sunday算法是Boyer-Moore的一种变体，更加简单高效。
算法思想
当匹配失败时，Sunday算法关注的是文本串中参与下一次匹配的第一个字符（即text[s+m]），根据这个字符在模式串中最右出现的位置来确定跳跃距离。
代码实现
// Sunday字符串匹配算法
vector<int> sunday(string text, string pattern) {
vector<int> positions;
int n = text.length();
int m = pattern.length();
// 处理空串情况
if (m == 0) return positions;
// 构建偏移表
vector<int> shift(256, m + 1); // 默认为m+1
for (int i = 0; i < m; i++) {
shift[(int)pattern[i]] = m - i;
}
int s = 0; // 模式串在文本串中的起始位置
while (s <= n - m) {
int j = 0;
// 从左向右比较
while (j < m && pattern[j] == text[s+j]) {
j++;
}
// 完全匹配
if (j == m) {
positions.push_back(s);
}
// 计算跳跃距离
// 如果s+m超出文本范围，则结束搜索
if (s + m < n) {
s += shift[(int)text[s+m]];
} else {
break;
}
}
return positions;
}
时间复杂度分析
- 预处理：O(m)
- 匹配过程：
- 最坏情况：O(n*m)
- 平均情况：O(n)，通常比Boyer-Moore更简单快速
算法选择指南
根据不同情况选择合适的字符串匹配算法：
- 朴素算法：适用于短文本和短模式串，或仅需简单实现的情况
- Rabin-Karp：适用于多模式匹配或对哈希敏感的应用
- KMP：保证线性时间复杂度，适用于安全关键场景
- Boyer-Moore：适用于长模式串和大字符集，实际应用中最快
- Sunday：实现简单，平均性能好，适合一般应用场景
实际应用
- 文本编辑器的查找功能
- 生物信息学中的DNA序列匹配
- 网络安全中的入侵检测系统
- 搜索引擎的索引构建
- 文件系统的文件内容搜索
练习题目推荐
- POJ 3461: Oulipo (字符串匹配基础)
- POJ 2406: Power Strings (KMP应用)
- POJ 3080: Blue Jeans (字符串匹配变体)
- Codeforces 471D: MUH and Cube Walls (KMP应用)
- Codeforces 126B: Password (KMP前缀函数应用)
总结
字符串匹配是算法竞赛中的基础问题，掌握多种匹配算法可以帮助你选择最适合具体问题的解决方案。KMP算法是核心算法，必须熟练掌握；而Boyer-Moore和Sunday算法在实际应用中往往更快，也值得深入学习。