Bitset
给定一个字符串$s$,一个区间$l,r$和一个字符串$y$
求s串的l,r区间内y的出现次数
用bitset来做,先开26个bitset对应26个小写字母,每个bitset保存其对应字符出现的位置。
我们要求$y$串出现次数,先求$y[0]$出现次数,再求$y[0-1]$出现次数,再求...$y[0-len-1]$出现的次数。求$y[0-i]$的出现次数肯定是求$y[0-(i-1)]$次数中满足$y[0-(i-1)]$后面紧跟$y[i]$的串的个数.
先初始一个$bitset$记为$ans$,初始全为1, 然后每次 $ans = ans&(bitset[y[i]-'a'] >> i )$ , 这个$ans$就是代表了串$y[0-i]$出现的次数,最后统计$ans$的区间$[l,r-len+1]$内有多少个$1$即可。不能暴力统计$1$的个数,会T。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n ,q;
char s[N] , y[N];
bitset<N> bs[30];
int main () {
scanf("%s%d",s,&q);
n = strlen(s);
for(int i = 0;i < n; ++ i){
bs[s[i] - 'a'].set(i);//保存每个字符出现的位置
}
int op , l ,r ;
while(q--)
{
scanf("%d", &op);
if(op == 1){
scanf("%d%s",&l,y);
-- l;
bs[s[l] -'a'][l] = 0;
s[l] = y[0];
bs[s[l] -'a'][l] = 1;
}
else{
scanf("%d%d%s",&l,&r,y);
-- l ,-- r;
int len = strlen(y);
if(r - l + 1 < len) {
puts("0");
continue;
}
bitset<N> ans;
ans.set();
for(int i = 0; i < len ; ++ i){
ans &= (bs[y[i]- 'a'] >> i);
}
int cnt = (ans >> l).count() - (ans >> (r - len + 2)).count();//不能暴力统计,要用前缀和思想
printf("%d\n",cnt);
}
}
return 0;
}