题目描述
题意:统计 主串s中 首字符为c1尾字符c2的长度不小于k的子串的数量
算法1
(二分) $O(nlogn)$
c++代码
#include<iostream>
#include<algorithm>
const int N=500010;
char s[N];
int l[N],r[N],cnt_l,cnt_r;//l[N]和r[N]分别记录主串中 字符c1和c2的下标(下标从1开始),cnt_1和cnt_2记录c1和c2出现次数
int main(){
int k;
char a[2],b[2];
scanf("%d%s%s%s",&k,s+1,a,b);
for(int i=1;s[i];i++){
if(s[i]==a[0]){
l[++cnt_l]=i;
}
if(s[i]==b[0]){
r[++cnt_r]=i;
}
}
long long res=0;
for(int i=1;i<=cnt_l;i++){//枚举每个左端点
int goal=l[i]+k-1;
if(goal>r[cnt_r])break;//当当前左端点l[i]与最右侧的右端点组成的子串长度<k,那么后面的子串只会更短,所以break
//r[cnt_r]-l[i]+1<k 等价于--> l[i]+k-1>r[cnt_r]
int L=1,R=cnt_r;
while(L<R){//二分找右端点(L)
int mid=L+R>>1;
if(r[mid]<goal){
L=mid+1;
}else R=mid;
}
//s[i~L]是满足长度不小于k的最短子串
res+=cnt_r-(L-1);//可直接用下标作前缀和
}
std::cout<<res;
return 0;
}