蓝桥杯2023年第十四届省赛真题-子串简写（递推）

solution

注意首尾元素也可能相等，c语言网有相应的测试用例，不过蓝桥杯木得。

#include<iostream>
#include<string>
using namespace std;
const int maxn = 5e5 + 10;
int sum[maxn] = {0};
int main(){
    int k;
    long long ans = 0;
    string s;
    char l, r;
    cin >> k >> s >> l >> r;
    s = " " + s;
    for(int i = 1; i < s.size(); i++){
        sum[i] = sum[i - 1];//前缀和记录合法开头方案数
        if(s[i] == l) sum[i]++;
        if(s[i] == r && i >= k) ans += sum[i - (k - 1)];//递推，发现目标结尾，累计当前有的几种合法开头 
    }
    cout << ans;
    return 0;
}