Codeforces - 914F bitset 维护字符串匹配个数

题意：给你一个串，支持两种操作，1 修改某个点的字符，2 询问 \([l,r]\) 内模式串 P 与原串的匹配个数

bitset 的写法是真的 6 啊，简直是优雅暴力的典范

\(bs[i]\) 表示 \(T_i\) 与 \(P\) 匹配与否，

具体地，每次错位按位与依次表示 \(T_i,T_{i+1} \cdots T_{i+len2-1}\)与\(P_1,P_2 \cdots P_{len2}\) 匹配与否

注意的是最后去除重复部分的起始下标应该是 \((r-len2+1)+1\)，而不是 \(r+1\)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define println(a) printf("%lld\n",(ll)a)
using namespace std;
const int MAXN = 1e5+30;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
typedef long long ll;
const ll MOD = 1e9+7; 
unsigned int SEED = 19260817;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bitset<MAXN> bs,cc[32];
char tmp[MAXN],str[MAXN];
int main(){
    while(scanf("%s",str+1)!=EOF){
        int len=strlen(str+1);
        rep(i,0,26) cc[i].reset();
        rep(i,1,len) cc[str[i]-'a'][i]=1;
        int m=read();
        while(m--){
            int op=read(),t;
            if(op==1){
                scanf("%d%s",&t,tmp+1);
                cc[str[t]-'a'][t]=0;
                cc[tmp[1]-'a'][t]=1;
                str[t]=tmp[1];
            }else{
                int l=read();
                int r=read();
                scanf("%s",tmp+1);
                int len2=strlen(tmp+1);
                if(r-l+1<len2){
                    println(0);
                }else{
                    bs.set();
                    rep(i,1,len2) bs&=(cc[tmp[i]-'a']>>(i-1));
                    int ans=(bs>>(l)).count()-(bs>>(r-len2+2)).count();
                    println(ans);
                }
            }
        }
    }
    return 0;
}