子串简写
一.暴力
思路:
只能通过60%。
从字符串开头遍历,如果遇到c1就进入子遍历,遇到长度大于等于k且以c2结尾的子串就使cnt++;遍历完之后再从外遍历找c1。
这种方法的弊端在于:外遍历
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int k; cin >> k;string s;char c1, c2;cin >> s >> c1 >> c2;int cnt = 0;for (int i = 0; i < s.length(); i++){if (s[i] == c1){for (int j = i+1;j < s.length(); j++){if (s[j] == c2 && (j-i+1)>=k) cnt++;}}}cout << cnt << '\n';return 0;
}
二.二分
学习了b站Turing_Sheep的思路
思路:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
using ll = long long;
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll k, ans = 0; cin >> k;string s;char c1, c2;cin >> s >> c1 >> c2;vector<ll>v;//存储c1位置for (ll i = 0; i < s.length(); i++){if (s[i] == c1) v.push_back(i);if (s[i] == c2){if (!v.size() || (i-k+1) < 0) continue;int l = 0, r = v.size()-1;while(l < r){ll mid = l + r + 1 >> 1;if (v[mid] <= (i-k+1)) l = mid;else r = mid-1;}if (v[l] <= (i-k+1)) ans += (l+1);}}cout << ans << '\n';return 0;
}