字符串算法概述
什么是字符串算法
【字符串算法】是处理文本数据的一系列算法，主要关注如何高效地存储、搜索、比较和操作字符串。在算法竞赛和实际编程中，字符串处理是一类常见且重要的问题。
字符串算法的基本操作
字符串匹配：在文本中查找特定的模式串。
- 朴素算法：O(n*m) 时间复杂度
- KMP算法：O(n+m) 时间复杂度
- Rabin-Karp算法：平均O(n+m)，最坏O(n*m)
- Boyer-Moore算法：平均情况下比KMP更快
字符串处理：
- 分割与合并
- 替换与删除
- 大小写转换
- 子串提取
字符串存储：
- 字典树(Trie)
- 后缀树与后缀数组
- 哈希表
常用字符串算法
1. KMP算法
Knuth-Morris-Pratt算法是一种高效的字符串匹配算法，通过预处理模式串，避免了不必要的比较。
核心思想：利用已经匹配过的信息，避免回溯文本串的指针。
时间复杂度：O(n+m)，其中n和m分别是文本串和模式串的长度。
主要步骤：
- 预处理模式串，计算next数组
- 使用next数组指导匹配过程
// KMP算法实现
void computeLPS(string pat, int* lps) {
int m = pat.length();
int len = 0; // 前缀长度
lps[0] = 0; // lps[0]总是0
int i = 1;
while (i < m) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
vector<int> KMP(string txt, string pat) {
int n = txt.length();
int m = pat.length();
vector<int> result; // 存储所有匹配位置
// 创建lps数组存储最长匹配前缀后缀值
int lps[m];
computeLPS(pat, lps);
int i = 0; // txt的索引
int j = 0; // pat的索引
while (i < n) {
// 当前字符匹配
if (pat[j] == txt[i]) {
i++;
j++;
}
// 找到完整匹配
if (j == m) {
result.push_back(i - j); // 记录匹配位置
j = lps[j - 1]; // 寻找下一个匹配
}
// 不匹配的情况
else if (i < n && pat[j] != txt[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return result;
}
2. 字典树(Trie)
字典树是一种树形数据结构，用于高效地存储和检索字符串集合。
特点：
- 根节点不包含字符
- 每个节点包含多个子节点，对应不同的字符
- 从根节点到某一节点的路径上的字符连接起来形成一个字符串
应用场景：
- 前缀匹配
- 自动补全
- 字符串集合的快速查找
// 字典树实现
struct TrieNode {
bool isEndOfWord; // 标记该节点是否为某个单词的结尾
TrieNode* children[26]; // 假设只包含小写英文字母
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
// 插入单词
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEndOfWord = true; // 标记单词结尾
}
// 搜索单词
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
return false; // 找不到对应字符
}
node = node->children[index];
}
return node->isEndOfWord; // 只有到达单词结尾才算找到
}
// 前缀搜索
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return true; // 只要能走完前缀就算找到
}
// 析构函数
~Trie() {
deleteTrie(root);
}
private:
// 递归删除树节点
void deleteTrie(TrieNode* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
deleteTrie(node->children[i]);
}
}
delete node;
}
};
3. Rabin-Karp算法
Rabin-Karp算法使用哈希函数计算字符串的哈希值，通过比较哈希值来进行字符串匹配。
核心思想：
- 计算模式串的哈希值
- 计算文本串中每个长度为m的子串的哈希值
- 比较哈希值，如果相同则进一步验证
特点：
- 平均时间复杂度：O(n+m)
- 最坏时间复杂度：O(n*m)
- 适合多模式串匹配
// Rabin-Karp算法实现
vector<int> rabinKarp(string txt, string pat) {
int n = txt.length();
int m = pat.length();
vector<int> result;
// 基数，通常选择一个比字符集大小大的素数
int d = 256;
// 一个大素数
int q = 101;
int h = 1;
// 计算 h = d^(m-1) % q
for (int i = 0; i < m - 1; i++) {
h = (h * d) % q;
}
// 计算模式串和文本串第一个窗口的哈希值
int p = 0; // 模式串哈希值
int t = 0; // 文本串当前窗口的哈希值
for (int i = 0; i < m; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
// 滑动窗口并比较
for (int i = 0; i <= n - m; i++) {
// 如果哈希值相等，进一步比较字符
if (p == t) {
bool match = true;
for (int j = 0; j < m; j++) {
if (txt[i + j] != pat[j]) {
match = false;
break;
}
}
if (match) {
result.push_back(i);
}
}
// 计算下一个窗口的哈希值
if (i < n - m) {
t = (d * (t - txt[i] * h) + txt[i + m]) % q;
if (t < 0) {
t += q;
}
}
}
return result;
}
字符串算法优化技巧
字符串哈希：将字符串转换为整数，便于快速比较。
- 常用哈希函数：h = (h * base + s[i]) % mod
- 常见的base值：31, 131, 1331等
- 常见的mod值：10^9+7, 10^9+9等
位运算优化：利用位运算优化字符串处理。
- 例如，用一个整数表示字符集，利用位操作进行字符集合运算
滑动窗口：在需要连续处理子串的问题中使用滑动窗口技术。
- 维护一个窗口，通过添加和删除元素更新窗口状态
双指针技术：使用两个指针处理字符串。
- 如对撞指针、快慢指针等
常见字符串问题类型
模式匹配：在文本中查找特定的模式串。
- 精确匹配：KMP, Rabin-Karp等
- 近似匹配：编辑距离，最长公共子序列等
字符串统计：统计字符串中的特定字符或模式。
- 字符频率统计
- 最长重复子串
- 最长回文子串
字符串转换：将一个字符串转换为另一个字符串。
- 编辑距离问题
- 字符串压缩与解压
字符串排序：特定条件下的字符串排序。
- 字典序排序
- 按特定条件排序
典型例题分析
例题1：最长回文子串
// Manacher算法求最长回文子串
string longestPalindrome(string s) {
// 预处理，在字符间插入特殊字符
string t = "$#";
for (char c : s) {
t += c;
t += '#';
}
t += '@';
int n = t.length();
vector<int> p(n, 0); // p[i]表示以i为中心的回文半径
int center = 0, maxRight = 0;
int maxLen = 0, start = 0;
for (int i = 1; i < n - 1; i++) {
// 初始化p[i]
if (i < maxRight) {
p[i] = min(p[2 * center - i], maxRight - i);
} else {
p[i] = 1;
}
// 中心扩展
while (t[i + p[i]] == t[i - p[i]]) {
p[i]++;
}
// 更新maxRight
if (i + p[i] > maxRight) {
center = i;
maxRight = i + p[i];
}
// 更新最长回文子串
if (p[i] - 1 > maxLen) {
maxLen = p[i] - 1;
start = (i - p[i] + 1) / 2;
}
}
return s.substr(start, maxLen);
}
例题2：字符串哈希应用
// 使用字符串哈希检查重复子串
bool hasRepeatingSubstring(string s, int len) {
int n = s.length();
if (len * 2 > n) return false; // 无法形成重复子串
unordered_map<long long, vector<int>> hash_pos;
const int base = 31;
const int mod = 1e9 + 7;
long long hash = 0;
long long power = 1;
// 计算第一个窗口的哈希值
for (int i = 0; i < len; i++) {
hash = (hash * base + (s[i] - 'a' + 1)) % mod;
if (i < len - 1) {
power = (power * base) % mod;
}
}
hash_pos[hash].push_back(0);
// 滑动窗口计算后续哈希值
for (int i = 1; i <= n - len; i++) {
hash = (hash - (s[i - 1] - 'a' + 1) * power % mod + mod) % mod;
hash = (hash * base + (s[i + len - 1] - 'a' + 1)) % mod;
// 检查哈希冲突
for (int pos : hash_pos[hash]) {
bool equal = true;
for (int j = 0; j < len; j++) {
if (s[pos + j] != s[i + j]) {
equal = false;
break;
}
}
if (equal) return true; // 找到重复子串
}
hash_pos[hash].push_back(i);
}
return false;
}
练习题推荐
字符串匹配：
字典树：
回文串：
字符串哈希：
总结
字符串算法在竞赛编程和实际应用中都有广泛的用途。掌握KMP、字典树等核心算法，以及各种优化技巧，能够帮助我们高效处理各种字符串问题。在实践中，应根据问题特点选择合适的算法和数据结构，灵活运用各种技巧提高解题效率。
在接下来的章节中，我们会更详细地介绍各种字符串算法及其应用场景。