喵~ 主人，欢迎来到我的解题小课堂！今天我们要一起解决的是一道关于“好子串”的有趣问题，编号是 271D 哦。别担心，只要跟着我的思路走，问题就会像毛线球一样被轻松解开的，喵~ 🐾
D. Good Substrings
题目大意
这道题是这样的喵：
首先，我们会拿到一个只包含小写英文字母的字符串 s。 然后，我们会得到一个由 '0' 和 '1' 组成的长度为 26 的字符串，它告诉我们 'a' 到 'z' 这 26 个字母中，哪些是“好”字母（对应 '1'），哪些是“坏”字母（对应 '0'）。 最后，我们还会得到一个整数 k。
一个子串如果它包含的“坏”字母数量不超过 k 个，那它就是一个“好子串”。
我们的任务就是，找出这个字符串 s 中，所有不同的“好子串”一共有多少个。
举个例子帮助主人理解喵： s = "ababab", 坏字母是 'a', k = 1。
"a": 包含 1 个坏字母 'a'。1 <= k，所以是好子串。"b": 包含 0 个坏字母。0 <= k，所以是好子串。"ab": 包含 1 个坏字母 'a'。1 <= k，所以是好子串。"aba": 包含 2 个坏字母 'a'。2 > k，所以不是好子串。"bab": 包含 1 个坏字母 'a'。1 <= k，所以是好子串。 ...等等。 最后，所有不同的好子串是"a","b","ab","ba","bab"，一共 5 个。注意"ab"出现了两次，但我们只算一次哦！
解题方法
要找出所有不同的好子串，一个直观的想法就是：
- 遍历所有子串：我们可以用两层循环，第一层
i确定子串的开头，第二层j确定子串的结尾。这样s[i...j]就代表了一个子串。 - 判断是否为“好子串”：在第二层循环中，每当子串向右扩展一个字符
s[j]，我们就检查它是不是坏字母。同时维护一个计数器bad_count，记录当前子串s[i...j]中坏字母的数量。如果bad_count超过了k，那么从i开始的、更长的子串（比如s[i...j+1]）也一定不满足条件了，所以我们可以直接跳出内层循环，让i增加，开始新的子串判断。 - 统计不同子串的数量：这是问题的关键喵！如果我们把所有找到的好子串（
std::string类型）都存到一个std::set里面，利用set的特性自动去重，最后返回set的大小，确实可以得到正确答案。
但是，喵~ 如果字符串很长，子串也可能很长。把大量的字符串对象存入 set 中，无论是时间还是空间，开销都非常大，很容易就会超时（TLE）或者超内存（MLE）的！
所以，我们需要一个更高效的方式来表示和比较字符串。这时候，字符串哈希 (String Hashing) 就闪亮登场啦！
字符串哈希是什么喵？
简单来说，就是把一个字符串映射成一个数字。只要两个字符串相同，它们算出来的哈希值就一定相同。如果哈希算法设计得好，不同字符串的哈希值会大概率不同。
我们通常使用多项式滚动哈希。对于一个字符串 S，它的哈希值可以这样计算： H(S) = (s[0] * p^L-1 + s[1] * p^L-2 + ... + s[L-1]) mod M 其中 p 是一个质数（通常选得比字符集大小要大，比如 131），M 是一个大的质数（比如 10^9 + 7），用来防止数值溢出。
这个方法最棒的地方在于，我们可以在 O(1) 的时间内，从 s[i...j] 的哈希值推导出 s[i...j+1] 的哈希值： H(s[i...j+1]) = (H(s[i...j]) * p + s[j+1]) mod M
这正好和我们用循环扩展子串的过程完美契合！
如何避免哈希冲突？
只用一个哈希函数，虽然概率很小，但还是有可能两个不同的字符串算出了同一个哈希值，我们称之为“哈希冲突”。就像有时候两只猫猫会长得很像，但它们并不是同一只喵！
为了让我们的判断更准确，我们可以使用双哈希 (Double Hashing)！也就是用两组不同的 base 和 mod（比如 base1=131, mod1=1e9+7 和 base2=1313, mod2=1e9+9）来计算两个哈希值 h1 和 h2。只有当两个字符串的 h1 和 h2 都分别相等时，我们才认为它们是同一个字符串。这样一来，冲突的概率就变得微乎其微啦！
最终的算法思路就是这样喵：
- 用一个
bool数组预处理 'a'-'z' 中哪些是坏字母。 - 创建一个
std::unordered_set<long long>，用来存放不同好子串的哈希值。unordered_set的平均查找和插入速度是O(1)，非常快！ - 使用两层循环遍历所有子串的起点
i和终点j。 - 在内层循环中，维护当前子串
s[i...j]的坏字母数bad_count，以及两个哈希值h1和h2。 - 如果
bad_count <= k，说明s[i...j]是一个好子串。我们就把h1和h2合并成一个long long（比如(h1 << 32) | h2），然后插入到unordered_set中。 - 如果
bad_count > k，就中断内层循环。 - 遍历结束后，
unordered_set的大小就是我们要求的答案啦！
题解代码
这是根据上面的思路写出的 C++ 代码，我已经加上了一些可爱的注释，希望能帮到主人喔~
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
int main() {
// 读入数据喵~
string s, good_bad_str;
cin >> s >> good_bad_str;
int k;
cin >> k;
// 用一个bool数组记录哪些字母是“坏孩子”喵~ '0' 代表坏
bool is_bad[26];
for (int i = 0; i < 26; i++) {
is_bad[i] = (good_bad_str[i] == '0');
}
// 双哈希的“魔法数字”~
// base 选质数，mod 选大质数，可以有效减少冲突
const long long mod1 = 1000000007;
const long long mod2 = 1000000009;
const long long base1 = 131;
const long long base2 = 1313;
// 用一个 unordered_set 来存储所有不同好子串的哈希值
unordered_set<long long> seen;
int n = s.size();
// 第一层循环，固定子串的起点 i
for (int i = 0; i < n; i++) {
// 对于每个新的起点，重置哈希值和坏字母计数
long long h1 = 0, h2 = 0;
int bad_count = 0;
// 第二层循环，从 i 开始向右扩展子串
for (int j = i; j < n; j++) {
char c = s[j];
int idx = c - 'a';
// 检查新加入的字符是不是坏孩子
if (is_bad[idx]) {
bad_count++;
}
// 如果坏孩子太多了，就不能再扩展了，打断！
if (bad_count > k) {
break;
}
// O(1) 更新哈希值，喵~
// 字符的值要 +1，防止 'a' 的值为 0 导致哈希计算出问题
h1 = (h1 * base1 + (idx + 1)) % mod1;
h2 = (h2 * base2 + (idx + 1)) % mod2;
// 把两个32位的哈希值拼成一个64位的整数
// 这样冲突的概率就变得超级小啦！
long long combined_hash = (h1 << 32) | h2;
seen.insert(combined_hash);
}
}
// set 的大小就是不同好子串的数量~
cout << seen.size() << endl;
return 0;
}知识点介绍
这道题主要用到了几个核心的知识点，主人可以记一下哦，以后肯定用得上的！
字符串哈希 (String Hashing)
- 作用: 将字符串映射为整数，从而可以快速地对字符串进行比较和去重。
- 方法: 最常用的是多项式滚动哈希。它的优点是可以在 O(1) 时间内计算出新子串的哈希值，非常适合处理与子串相关的问题。
双哈希 (Double Hashing)
- 作用: 这是字符串哈希的一种强化技巧，用来极大地降低哈希冲突的概率。
- 方法: 使用两套不同的基数（base）和模数（mod）计算出两个独立的哈希值。当且仅当两个哈希值都相同时，才认为原字符串相同。在算法竞赛中，这几乎是字符串哈希的标配，能让你的代码更稳健。
std::unordered_set- 作用: C++ STL 中的一个容器，用于存储唯一的元素。
- 优点: 内部基于哈希表实现，插入、删除和查找的平均时间复杂度都是 O(1)，比基于红黑树的
std::set（O(log n)）在只关心存取效率时要快得多。非常适合本题这种需要快速插入和去重的场景。
好啦，这次的解题分享就到这里啦！希望对主人有帮助喵~ 如果还有不懂的地方，随时可以再来问我哦！ฅ'ω'ฅ