题目描述
程序猿圈子里正在流行一种很新的简写方法:
对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。
例如 internationalization
简写成 i18n
,Kubernetes
简写成 K8s
,Lanqiao
简写成 L5o
等。
在本题中,我们规定长度大于等于 $K$ 的字符串都可以采用这种简写方法(长度小于 $K$ 的字符串不配使用这种简写)。
给定一个字符串 $S$ 和两个字符 $c_1$ 和 $c_2$,请你计算 $S$ 有多少个以 $c_1$ 开头 $c_2$ 结尾的子串可以采用这种简写?
输入格式
第一行包含一个整数 $K$。
第二行包含一个字符串 $S$ 和两个字符 $c_1$ 和 $c_2$。
输出格式
一个整数代表答案。
数据范围
对于 $20\\%$ 的数据,$2 ≤ K ≤ |S| ≤ 10000$。
对于 $100\\%$ 的数据,$2 ≤ K ≤ |S| ≤ 5 × 10^5$。$S$ 只包含小写字母。$c_1$ 和 $c_2$ 都是小写字母。
$|S|$ 代表字符串 $S$ 的长度。
输入样例:
4
abababdb a b
输出样例:
6
样例解释
符合条件的子串如下所示,中括号内是该子串
算法
用树状数组边扫边操作即可,遇到 c1 ,则加到区间里, 遇到 c2 , 则统计它往前 k 个位置之前 有多少个 c1
最后,全部加起来即为答案。
记得开 long long
C++ 代码
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N = 500010;
int tr[N];
char str[N], c1, c2;
int k;
inline int lowbit(int x)
{
return x & -x;
}
void add(int x, int y)
{
while(x < N)
{
tr[x] += y;
x += lowbit(x);
}
return ;
}
int ask(int x)
{
int res = 0;
while(x)
{
res += tr[x];
x -= lowbit(x);
}
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> k >> str + 1 >> c1 >> c2;
int ls = strlen(str + 1);
int res = 0;
for(int i = 1;i <= ls;i ++)
{
if(str[i] == c1) add(i, 1);
if(i >= k && str[i] == c2) res += ask(i - k + 1);
}
cout << res << endl;
return 0;
}