题解：P9244 [蓝桥杯 2023 省 B] 子串简写

liborui0000 · 2025-07-26 21:47:26 · 题解

P9244 题解

核心:

通过前缀和预处理出 c2 的数量，然后遍历字符串。如果遇到 c1 就把它之后 k 个数和 n（字符串长度）之间的 c2 的数量加到答案中去。

注意

一定要判断好边界条件！！！特别是用前缀和求 c1 之后 k 个数和 n 之间的 c2 数量的时候。

一定要开 long long！！！

代码如下：

#include <bits/stdc++.h>

using namespace std;

long long k;
string s;
char l, r;
long long sumb[500010];

int main(){
    cin >> k;
    cin >> s >> l >> r;
    long long n = s.size();
    for (int i = 0; i < n; i++){
        if (s[i] == r) sumb[i + 1] = sumb[i] + 1;       
        else sumb[i + 1] = sumb[i];
    }

    long long ans = 0;
    for (int i = 1; i <= n - k + 1; i++){
        if (s[i - 1] == l){
            if (i + k - 1 <= n){
                ans += sumb[n] - sumb[i + k - 2];
            }
        }
    }
    cout << ans;
    return 0;
}