子串理论基础
子串，字符串，kmp算法
·
文章目录
子串理论基础
1. 子串的基本概念
**子串（Substring）**是字符串中连续的一段字符序列。子串问题是字符串处理中的经典问题，通常涉及查找、匹配、统计等操作。
1.1 基本术语
- 子串（Substring）：字符串中连续的一段字符序列
- 子序列（Subsequence）：字符串中不一定连续但保持相对顺序的字符序列
- 前缀（Prefix）：从字符串开头到某个位置的子串
- 后缀（Suffix）：从某个位置到字符串结尾的子串
- 滑动窗口（Sliding Window）：维护一个动态的窗口区间来解决问题
1.2 子串问题的特点
- 连续性：子串必须是连续的字符序列
- 动态性：通常需要动态调整窗口大小
- 高效性：使用滑动窗口可以将O(n²)优化到O(n)
示例：
字符串："abcde"
子串示例：
- "abc"：从索引0到2的子串
- "bcd"：从索引1到3的子串
- "cde"：从索引2到4的子串
子序列示例（不连续）：
- "ace"：索引0, 2, 4的字符
- "bd"：索引1, 3的字符
2. 子串问题的分类
2.1 滑动窗口类
特点：
- 使用双指针维护一个动态窗口
- 通过移动窗口边界来解决问题
- 适用场景：无重复字符的最长子串、找到字符串中所有字母异位词、最小覆盖子串
示例：
// 滑动窗口：维护一个无重复字符的窗口
int left = 0, right = 0;
unordered_set<char> window;
while(right < s.size()) {
// 扩大窗口
// 缩小窗口直到满足条件
while(/* 窗口不满足条件 */) {
left++;
}
right++;
}
2.2 字符串匹配类
特点：
- 在文本串中查找模式串
- 使用KMP算法优化匹配过程
- 适用场景：找出字符串中第一个匹配的下标、重复的子字符串
示例：
// KMP算法：利用next数组避免重复匹配
vector<int> next(pattern.size());
getNext(next, pattern);
// 使用next数组进行匹配
2.3 其他技巧类
特点：
- 使用特殊的字符串性质
- 结合其他算法技巧
- 适用场景：重复的子字符串（利用字符串拼接性质）
3. 滑动窗口类子串模板
3.1 无重复字符的最长子串
适用场景：找到字符串中不含有重复字符的最长子串的长度
核心思路：
- 使用滑动窗口维护一个无重复字符的窗口
- 使用set记录窗口中的字符
- 当出现重复字符时，缩小窗口直到无重复
模板代码：
// LeetCode 3. 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> occ; // 当前窗口中的字符集合（保证无重复）
int left = 0, right = 0; // 左右指针
int res = 0; // 最长无重复子串长度
while(right < s.size()) {
// ① 当右指针指向的字符不在窗口中 → 可以扩张窗口
if(!occ.count(s[right])) {
occ.insert(s[right]); // 加入窗口
res = max(res, right - left + 1); // 更新最大长度
right++; // 移动右指针扩大窗口
} else {
// ② 当出现重复字符 s[right]
// 把 left 指向的字符从窗口移除，然后把 left ++
occ.erase(s[left]);
left++; // 收缩窗口（直到无重复为止）
}
}
return res;
}
};
关键点：
- 使用
unordered_set记录窗口中的字符 - 当出现重复字符时，从左侧开始移除字符直到无重复
- 窗口长度：
right - left + 1 - 时间复杂度：O(n)，空间复杂度：O(min(n, m))，m为字符集大小
3.2 找到字符串中所有字母异位词
适用场景：找到字符串中所有是另一个字符串的字母异位词的子串的起始索引
核心思路：
- 使用固定大小的滑动窗口（窗口大小等于模式串长度）
- 使用multiset或数组统计窗口中的字符频次
- 比较窗口字符和模式串字符是否相同
模板代码：
// LeetCode 438. 找到字符串中所有字母异位词
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if(s.size() < p.size()) return result;
// 1. 用 multiset 存 p 的所有字符
multiset<char> target(p.begin(), p.end());
multiset<char> window; // 当前滑动窗口的字符
int left = 0;
int right = 0;
int k = p.size();
// 2. 先把前 k 个字符加入窗口
for(; right < k; right++) {
window.insert(s[right]);
}
// 3. 判断第一个窗口
if(window == target) {
result.push_back(left);
}
// 4. 移动滑动窗口（右移一格）
while(right < s.size()) {
// （1）移除窗口最左边的字符
window.erase(window.find(s[left]));
left++;
// （2）加入新的右边字符
window.insert(s[right]);
right++;
// （3）判断当前窗口是否为 p 的异位词
if(window == target) {
result.push_back(left);
}
}
return result;
}
};
关键点：
- 固定窗口大小：窗口大小等于模式串长度
- 使用multiset：可以统计字符频次并支持比较
- 窗口移动：每次右移一格，移除最左字符，加入最右字符
- 时间复杂度：O(n)，空间复杂度：O(m)，m为模式串长度
3.3 滑动窗口通用模板（子串类）
核心思路：
- 右指针扩大窗口
- 当窗口满足条件时，更新结果并缩小窗口
- 继续移动右指针
通用模板：
int left = 0, right = 0;
unordered_set<char> window; // 或 unordered_map<char, int>
while(right < s.size()) {
// 扩大窗口
window.insert(s[right]); // 或 window[s[right]]++
// 当窗口满足条件时
while(/* 窗口满足条件 */) {
// 更新结果
// 缩小窗口
window.erase(s[left]); // 或 window[s[left]]--
left++;
}
right++;
}
4. 字符串匹配类模板（KMP算法）
4.1 KMP算法的基本概念
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，其核心思想是当出现字符串不匹配时，可以利用之前已经匹配的文本内容，避免从头再去做匹配。
4.2 前缀表（next数组）
**前缀表（next数组）**记录了模式串中每个位置的最长相等前后缀的长度。
示例：
模式串："aabaaf"
索引： 0 1 2 3 4 5
字符： a a b a a f
next数组计算：
- next[0] = -1（或0，取决于实现）
- next[1] = 0（"aa"的前后缀：前缀"a"，后缀"a"，最长相等前后缀长度为1，但通常存储为0）
- next[2] = 0（"aab"无相等前后缀）
- next[3] = 1（"aaba"：前缀"a"，后缀"a"，长度为1）
- next[4] = 2（"aabaa"：前缀"aa"，后缀"aa"，长度为2）
- next[5] = 0（"aabaaf"无相等前后缀）
4.3 构造next数组
核心思路：
- 使用双指针i和j
- j指向前缀末尾，i指向后缀末尾
- 当字符不匹配时，j回退到next[j]
模板代码：
// 构造next数组
void getNext(int* next, const string& s) {
int j = -1; // j指向前缀末尾
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
// 前后缀不相同了，向前回退
while(j >= 0 && s[i] != s[j + 1]) {
j = next[j]; // 向前回退
}
// 找到相同的前后缀
if(s[i] == s[j + 1]) {
j++;
}
// 将j（前缀的长度）赋给next[i]
next[i] = j;
}
}
关键点：
- j初始化为-1，next[0] = -1
- i从1开始遍历
- 当s[i] != s[j + 1]时，j回退到next[j]
- 当s[i] == s[j + 1]时，j++
4.4 使用KMP进行字符串匹配
核心思路：
- 使用next数组进行匹配
- 当字符不匹配时，利用next数组回退，避免从头匹配
模板代码：
// LeetCode 28. 找出字符串中第一个匹配的下标
class Solution {
public:
void getNext(int* next, const string& s) {
int j = -1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while(j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if(s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) {
if(needle.size() == 0) {
return 0;
}
vector<int> next(needle.size());
getNext(&next[0], needle); // 构造next数组
int j = -1; // 因为next数组里记录的起始位置为-1
for(int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
j = next[j]; // j 寻找之前匹配的位置
}
if(haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
j++; // i的增加在for循环里
}
if(j == (needle.size() - 1)) { // 文本串s里出现了模式串t
return (i - needle.size() + 1);
}
}
return -1;
}
};
关键点：
- 构造next数组：使用getNext函数
- 匹配过程：当字符不匹配时，j回退到next[j]
- 匹配成功：当j == needle.size() - 1时，找到匹配
- 时间复杂度：O(n + m)，空间复杂度：O(m)
5. 其他技巧类模板
5.1 重复的子字符串
适用场景：判断字符串是否由重复的子字符串构成
核心思路：
- 将字符串拼接：s + s
- 掐头去尾：去掉第一个和最后一个字符
- 如果原字符串s在新的字符串中出现，则说明s由重复子串构成
模板代码：
// LeetCode 459. 重复的子字符串
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t = s + s;
t.erase(t.begin()); // 掐头
t.erase(t.end() - 1); // 去尾
if(t.find(s) != std::string::npos) {
return true; // 如果s在t中出现，说明s由重复子串构成
}
return false;
}
};
关键点：
- 字符串拼接：s + s
- 掐头去尾：去掉首尾字符
- 查找：使用find函数查找s是否在t中出现
- 时间复杂度：O(n)，空间复杂度：O(n)
原理说明：
如果 s = "abab"，由"ab"重复构成
那么 s + s = "abababab"
掐头去尾后：t = "bababab"
s = "abab" 在 t 中出现，说明s由重复子串构成
6. 子串问题的时间复杂度
| 算法类型 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 滑动窗口（无重复字符） | O(n) | O(min(n, m)) | m为字符集大小 |
| 滑动窗口（固定窗口） | O(n) | O(m) | m为窗口大小 |
| KMP算法 | O(n + m) | O(m) | n为文本串长度，m为模式串长度 |
| 暴力匹配 | O(n × m) | O(1) | 最坏情况 |
注意：
- 滑动窗口通常可以将O(n²)优化到O(n)
- KMP算法将字符串匹配从O(n × m)优化到O(n + m)
- 空间复杂度主要取决于需要存储的字符集合大小
7. 何时使用子串技巧
7.1 使用场景
-
滑动窗口类
- 无重复字符的最长子串
- 找到字符串中所有字母异位词
- 最小覆盖子串
- 长度最小的子数组（数组中的子串问题）
-
字符串匹配类
- 找出字符串中第一个匹配的下标
- 重复的子字符串
- 字符串模式匹配
-
其他技巧类
- 利用字符串特殊性质的问题
- 字符串拼接、反转等操作
7.2 判断标准
当遇到以下情况时，考虑使用子串技巧：
- 需要查找连续的子串
- 需要统计子串的某种性质（如无重复、包含某些字符等）
- 需要在文本串中查找模式串
- 需要判断字符串的重复性质
- 问题可以转化为滑动窗口问题
示例：
// 问题：找到无重复字符的最长子串
// 暴力解法：O(n²)
for(int i = 0; i < s.size(); i++) {
for(int j = i; j < s.size(); j++) {
// 检查s[i...j]是否有重复字符
}
}
// 滑动窗口解法：O(n)
unordered_set<char> window;
int left = 0, right = 0;
while(right < s.size()) {
// 维护无重复字符的窗口
}
8. 子串问题的优缺点
8.1 优点
- 时间复杂度低：滑动窗口通常为O(n)，KMP为O(n + m)
- 代码简洁：逻辑清晰，易于实现
- 适用场景广：可以解决多种字符串子串问题
- 空间效率：通常只需要O(1)或O(m)的额外空间
8.2 缺点
- 需要理解算法原理：KMP算法需要理解next数组的含义
- 边界条件复杂：滑动窗口的边界条件需要仔细处理
- 不适用于所有问题：某些问题不适合用滑动窗口或KMP
9. 常见题型总结
9.1 滑动窗口类
-
无重复字符的最长子串
- 使用set记录窗口中的字符
- 当出现重复时，从左侧缩小窗口
-
找到字符串中所有字母异位词
- 固定窗口大小
- 使用multiset或数组统计字符频次
-
最小覆盖子串
- 使用map记录目标字符的频次
- 维护一个包含所有目标字符的窗口
9.2 字符串匹配类
-
找出字符串中第一个匹配的下标（KMP）
- 构造next数组
- 使用next数组进行匹配
-
重复的子字符串
- 利用字符串拼接性质
- 使用find函数查找
9.3 其他技巧类
-
字符串拼接技巧
- 重复的子字符串问题
-
字符串反转技巧
- 某些特殊的字符串问题
10. 总结
子串问题是字符串处理中的经典问题，主要通过滑动窗口和KMP算法来高效解决。
核心要点：
- 滑动窗口：维护一个动态窗口，通过移动边界来解决问题
- KMP算法：利用next数组避免重复匹配，提高匹配效率
- 字符串性质：利用字符串的特殊性质（如拼接、反转）来解决问题
- 时间复杂度：滑动窗口通常为O(n)，KMP为O(n + m)
- 空间复杂度：通常为O(1)或O(m)，m为字符集或模式串大小
使用建议：
- 无重复字符类问题优先考虑滑动窗口
- 字符串匹配问题考虑KMP算法
- 注意滑动窗口的边界条件和去重逻辑
- 理解KMP算法的next数组构造原理
- 合理利用字符串的特殊性质
常见题型总结：
- 滑动窗口类：无重复字符的最长子串、找到字符串中所有字母异位词
- 字符串匹配类：找出字符串中第一个匹配的下标（KMP）、重复的子字符串
- 其他技巧类：利用字符串拼接、反转等性质的问题
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
26
0- 0
已为社区贡献1条内容
所有评论(0)