蓝桥杯真题 - 子串简写 - 题解
题目链接：https://www.lanqiao.cn/problems/3514/learning/
个人评价：难度 2 星（满星：5）
前置知识：前缀和
整体思路
- 定义 s u m i sum_i sumi 表示前 i i i 个字符含有字符 c 1 c_1 c1 的个数，如果第 i i i 个字符为 c 2 c_2 c2，只需要将答案加上 s u m i − k + 1 sum_{i-k+1} sumi−k+1 即可，表示往前 k k k 个字符中，所有以 c 1 c_1 c1 开头的字符都能与 c 2 c_2 c2 组成一个满足条件的子串。
过题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000 + 100;
int k;
LL ans;
char c1, c2;
char str[maxn];
int sum[maxn];
int main() {
#ifdef ExRoc
freopen("test.txt", "r", stdin);
#endif // ExRoc
ios::sync_with_stdio(false);
cin >> k;
cin >> (str + 1);
cin >> c1 >> c2;
for (int i = 1; str[i] != '\0'; ++i) {
sum[i] = sum[i - 1];
if (str[i] == c1) {
++sum[i];
}
if (i >= k && str[i] == c2) {
ans += sum[i - k + 1];
}
}
cout << ans << endl;
return 0;
}