4960. 子串简写 - AcWing题库

题目描述

题目分析 

原本为纯暴力但是发现会超时，可以加入前缀和，从前往后先记录一下每个位置c1出现的次数

再从前往后扫一遍，如果遇到c2就将答案加上此位置前的所有c1的个数（直接加上此位置的前缀和）

纯暴力：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
int main()
{ll k;string s;char c1, c2;cin >> k;cin >> s;cin >> c1 >> c2;ll len = s.size();for(ll i = 0, j = 1; i < len - 1; i ++){if(s[i] == c1){j = i + 1;while((s[j] != c2 || j - i + 1 < k) && j < len - 1){j ++;}if(s[j] == c2 && j - i + 1 >= k){ans ++;while(j < len - 1) {j ++;if(s[j] == c2){ans ++;}}}}}cout << ans;return 0;
}

 ac代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
ll k, ans, s[N];
string c;
char c1, c2;
int main()
{cin >> k;cin >> c;cin >> c1 >> c2;ll len = c.size();for(int i = 0; i < len; i ++){if(c[i] == c1){s[i + 1] = s[i] + 1;}else s[i + 1] = s[i];}for(int i = k - 1; i < len; i ++)//注意长度至少为k{ll l = i - k + 1;if(c[i] == c2)ans += s[l + 1];}cout << ans;return 0;
}