14届蓝桥杯 C/C++ B组 T7 子串简写 （字符串）

采用存储目标字符下标的方法，此题的想法比较新奇，故予以记录。

存好下标之后，可以先定位好启始的字符，然后去搜结尾字符符合长度k并且最靠近启始字符的下标，找到之后可以直接取到这个下标之后的所有下标，因为都满足了长度大于等于k。

代码：

#include<iostream>
#include<vector>
using namespace std;
const int N = 5e5 + 10;

int main() {
	 //读入
	int k; cin >> k;
	string str; cin >> str;

	char c1, c2; cin >> c1 >> c2;

	//a1存是字符c1的下标，a2存是字符c2的下标
	vector<int>a1;
	vector<int>a2;
	//存
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == c1)a1.push_back(i);
		if (str[i] == c2)a2.push_back(i);
	}

	long long res = 0;//开longlong存答案

	for (int i = 0; i < a1.size(); i++) {//扫所有的c1对应的下标
		int t = a1[i];		//先取出c1对应下标
		int c = t + k - 1;	//定义出满足和c1距离k的下标

		//二分，从0二分到存c2下标的数组的长度
		int l = 0, r = a2.size() - 1;	
		while (l < r) {
			int mid = l + r >> 1;
			if (a2[mid] >= c)r = mid;	//如果当前c2的下标是大于等于最近的位置，就去搜更小的
			else l = mid + 1;
		}
		//这里直接取a2的长度减去l，l在这里代表的是a2的下标
		//通过上面的二分，l已经是最靠近c1的了，所以这就是能够取到的最长的长度了
		if (a2[l] >= c)res += a2.size() - l;
	}
	cout << res;
	return 0;
}