AcWing 4960. 子串简写
原题链接
中等
作者:
王一生_2
,
2024-03-04 01:28:51
,
所有人可见
,
阅读 25
非二分超简单方法
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 500005;
char str[N];
LL ans;
int k;
char l, r;
vector<int> lp;
vector<int> rp;
int main(){
cin >> k;
cin >> str >> l >> r;
int i = 0;
while(str[i] != '\0'){
if(str[i] == l)
lp.push_back(i);
if(str[i] == r)
rp.push_back(i);
i ++;
}
int mark = 0;
for(int j = 0; j < lp.size(); j ++){
while(rp[mark] - lp[j] + 1 < k){
mark ++;
if(mark == rp.size()) break;
}
if(mark == rp.size()) break;
ans += rp.size() - mark;
}
cout << ans << endl;
return 0;
}