课程进度 23% · 第3/10章第3/10章 · 标签 1/3
— 1 —
字符串存储与常用操作
C++中字符串常用string类，支持灵活操作。常见函数如下：
cpp
1
// 基本用法
2
string s = "hello";
3
s += " world"; // 拼接
4
cout << s.substr(0, 5) << endl; // 子串
5
reverse(s.begin(), s.end()); // 反转
6
// 手写字符串反转
7
void reverseStr(string& s) {
8
int l = 0, r = s.size() - 1;
9
while (l < r) swap(s[l++], s[r--]); // 双指针交换
10
}
常用操作：查找、替换、分割、去重、统计字符出现次数等。
cpp
1
// 统计每个字符出现次数
2
vector<int> count(256, 0);
3
for (char c : s) count[c]++;
4
// 查找子串
5
int pos = s.find("ll"); // 找到返回下标，否则string::npos
— 2 —
字符串匹配算法
字符串匹配常用暴力法和KMP算法：
cpp
1
// 暴力匹配
2
int strStr(string haystack, string needle) {
3
int n = haystack.size(), m = needle.size();
4
for (int i = 0; i <= n - m; ++i) {
5
int j = 0;
6
while (j < m && haystack[i + j] == needle[j]) ++j;
7
if (j == m) return i;
8
}
9
return -1;
10
}
11
// KMP算法
12
vector<int> getNext(string& p) {
13
int m = p.size();
14
vector<int> next(m, -1);
15
for (int i = 1, j = -1; i < m; ++i) {
16
while (j != -1 && p[j + 1] != p[i]) j = next[j];
17
if (p[j + 1] == p[i]) ++j;
18
next[i] = j;
19
}
20
return next;
21
}
22
int kmp(string s, string p) {
23
vector<int> next = getNext(p);
24
int n = s.size(), m = p.size(), j = -1;
25
for (int i = 0; i < n; ++i) {
26
while (j != -1 && p[j + 1] != s[i]) j = next[j];
27
if (p[j + 1] == s[i]) ++j;
28
if (j == m - 1) return i - m + 1;
29
}
30
return -1;
31
}
📖KMP算法通过next数组避免重复匹配，大幅提升效率。
stringKMP子串查找统计