AcWing 4960. 子串简写
原题链接
中等
暴力做法
#include<iostream>
#include<cstring>
using namespace std;
int k;
string s;
int main()
{
cin >> k;
cin >> s;
char a, b;
cin >> a >> b;
int cnt = 0;
for(int i = 0; i <= s.size(); i ++)
{
if(s[i] == a)
for(int j = i + 1; j <= s.size(); j ++)
if(j - i + 1 >= k && s[j] == b) cnt ++;
}
cout << cnt << endl;
return 0;
}
二分
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
int k;
string s;
cin >> k >> s;
char a, b;
cin >> a >> b;
vector<int>pc1; // 存储c1的位置
int cnt = 0;
for(int i = 0; i < s.size(); i ++)
{
if(s[i] == a) pc1.push_back(i);
if(s[i] == b)
{
if(i - k + 1 < 0 || !pc1.size())
continue;
int l = 0, r = (int)pc1.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(pc1[mid] <= (i - k + 1))
l = mid;
else
r = mid - 1;
}
if(pc1[l] <= (i - k + 1)) // 需要特判一下,防止区间都在右端
cnt += l + 1;
}
}
cout << cnt << endl;
return 0;
}