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;
}

原文地址：https://blog.csdn.net/2302_79440616/article/details/137475654

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！