//暴力代码:#include<bits/stdc++.h>#defineintlonglongusingnamespace std;voidsolve(){
int k;
string s;char c1, c2;
cin >> k >> s >> c1 >> c2;int ans =0;for(int i =0; i < s.size(); i ++){
if(s[i]!= c1)continue;for(int j = i +1; j < s.size(); j ++){
int len = j - i +1;if(len >= k && s[j]== c2)
ans ++;}}
cout << ans << endl;}signedmain(){
ios::sync_with_stdio(0);
cin.tie(0);int t =1;// cin >> t;while(t--)solve();}
三、正解代码
//子串简写:二分#include<bits/stdc++.h>#defineintlonglongusingnamespace std;voidsolve(){
int k;string s;char c1, c2;
cin >> k >> s >> c1 >> c2;
vector<int>pc1;//存储c1的位置int ans =0;for(int i =0; i < s.size(); i ++){
if(s[i]== c1)
pc1.push_back(i);if(s[i]== c2){
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)
ans +=(l +1);}}
cout << ans << endl;}signedmain(){
ios::sync_with_stdio(0);
cin.tie(0);int t =1;// cin >> t;while(t--)solve();}