当前位置：首页 > article >正文

[蓝桥杯 2023 省 B] 子串简写

article 2025/3/24 8:02:07

[蓝桥杯 2023 省 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}$ 。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

4
abababdb a b

输出 #1

说明/提示

【样例说明】

符合条件的子串如下所示，中括号内是该子串：

[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]

【评测用例规模与约定】

对于 $\%$ 的数据， $\leq K \leq|S| \leq 10^4$ 。

对于 $\%$ 的数据， $\leq K \leq|S| \leq 5 \times 10^{5}$ 。 $S$ 只包含小写字母。 $c_{1}$ 和 $c_{2}$ 都是小写字母。

$∣ S ∣$ 代表字符串 $S$ 的长度。

蓝桥杯 2023 省赛 B 组 G 题。

分析

由于数据量较大，直接枚举的方法只能过部分分，大部分会TLE，所以我们换一种思路枚举。

先对字符串S进行预处理，找到其中每一个c1和c2的位置，把这些位置存下来，只需要枚举这些位置即可。另外，由于对于简写的长度也有要求，所以简写的开始位置i和结束位置j之间存在j≥i+k-1的关系

整体思路就是，先对S进行预处理，存下其中c1和c2的位置，然后对于每一个c1的位置，找到其后第一个满足关系的结束位置，统计其后所有位置的数目，并全部加到最终的结果ans中

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
int k;
char str[500005];
char c1, c2;
long long ans = 0;
int c_1[500005];
int c_2[500005];
int main() {
    scanf("%d", &k);
    scanf("%s %c %c", str, &c1, &c2);
    int l = 0, h = 0;
    int n=strlen(str);
    for (int i = 0; i < n; i++) {
        if (str[i] == c1)
            c_1[l++] = i;
        if (str[i] == c2)`
            c_2[h++] = i;
    }
    for (int s = 0; s < l; s++) {
        int i = c_1[s];
        int pos = i + k - 1;
        int *num = std::lower_bound(c_2, c_2 + h, pos);
        ans += h - (num-c_2);
    }
    printf("%lld", ans);
    return 0;
}