蓝桥杯每日一题：子串简写_蓝桥杯子串简写

题目来源：第十四届蓝桥杯大赛软件赛省赛B组

程序猿圈子里正流行一种很新的简写方法：对于一个字符串，只保留首位字符，将首位字符之间的所有字符用这部分的长度代替。例如internationalization简写成i18n，Kubernetes简写成K8s，Lanqiao简写成L5o等。

在本题中，我们规定长度大于等于 $K$ 的字符串都可以采用这种简写方法（长度小于 $K$ 的字符串不配使用这种缩写)

给定一个字符串 $S$ 和两个字符 $c_1$ 和 $c_2$ , 请你计算 $S$ 有多少个以 $c_1$ 开头 $c_2$ 结尾的子串可以采用这种缩写?

输入: 第一行包含一个整数 $K$

第二行包含一个字符串 $S$ 和两个字符 $c_1$ 和 $c_2$

输出: 一个整数代表答案

Input Sample:

4
abababdb a b
1
2

Output Sample:

6
1

先说这道题的解题方法: 二分法or双指针, 两种方案的题解我都会给出来

首先先把字符串中 $c_1$ 和 $c_2$ 的下标单独用两个vector进行维护, 我们假设维护 $c_1$ 下标的vector为 $a$ , 维护 $c_2$ 的为 $b$ , 那么我们要遍历 $a$ , 假设此时指向 $a$ 的指针为 $i$ , 指向 $b$ 的指针为 $j$ , 我们要在这个循环内部用双指针或者二分法来查找到使得 $j-i+1=K$ 的这个 $j$ 值

下面给出题解代码, 共两个方案, 但核心思路都是一样的. 请注重思考, 不要无脑cv

方案1: 双指针法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
vector<int> a, b;

void io() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

int main() {
	io();
	int k;
	cin >> k;
	string s;
	char c1, c2;
	cin >> s >> c1 >> c2;
	int res = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == c1) {
			a.push_back(i);
		}
		if (s[i] == c2) {
			b.push_back(i);
		}
	}
	for (int i = 0, j = 0; i < a.size(); i++) {
		while (j < b.size() && b[j] - a[i] + 1 < k) {
			j++;
		}
		res += (b.size() - j);
	}
	cout << res << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

方案2: 二分法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
vector<int> a, b;

void io() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

int main() {
	io();
	int k;
	cin >> k;
	string s;
	char c1, c2;
	cin >> s >> c1 >> c2;
	int res = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == c1) {
			a.push_back(i);
		}
		if (s[i] == c2) {
			b.push_back(i);
		}
	}
	for (int i = 0; i < a.size(); i++) {
		while (l <= r) {
			int mid = l + r >> 1;
			if (b[mid] - a[i] + 1 > k) {
				r = mid - 1;
			} else if (b[mid] - a[i] + 1 == k) {
				res += (b.size() - mid);
				break;
			} else {
				l = mid + 1;
			}
		}
	}
	cout << res << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43