AcWing 4960. 子串简写
原题链接
中等
作者:
编号002
,
2024-02-20 13:00:17
,
所有人可见
,
阅读 50
#include<iostream>
#include<cstdio>
using namespace std;
const int N=500010;
int a[N];
long long cnt,sum;
int main()
{
int k;
scanf("%d",&k);
string b;
cin>>b;
char x,y; //首尾字符
cin>>x>>y;
for(int i=0;i<b.size();i++)
if(b[i]==y)a[cnt++]=i; //预处理,将子串中所有与y一样的字符下标储存
for(int i=0;i<b.size();i++)
{i
if(b[i]==x)
//固定i,根据下标距离进行二分,寻找另一个下标a[j],此下标是数组中大于等于i+k-1的第一个元素
{
int l=0,r=cnt-1;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]>=i+k-1)r=mid;
else l=mid+1;
}
//这里也可使用lower_bound函数
if(a[l]>=i+k-1)sum+=cnt-l;
//注意判断是否满足条件
}
}
printf("%lld",sum);
return 0;
}
int l=lower_bound(a,a+cnt,i+k-1)-a;