题解：P4465 [国家集训队] JZPSTR

ini2015_____ · 2025-12-19 12:36:56 · 题解

比特赛特就是牛啊。

似乎正解是块状链表加后缀自动机这样非常猎奇的结构，果然字符串的尽头就是数据结构。

然而我们有更牛的 bitset 解法。

考虑维护 |\sum| 个 bitset f_i，f_{i,j}=1 表示串的第 j 位为 i，插入删除可以用左移右移，容易做到单次 O(\frac {|\sum|n}w)。

对于字符串匹配，我们使用神秘算法 shift-and，就是我们维护一个 bitset 表示模式串每个位置是否能过进行匹配，初始的时候是全 1 的，我一个位置能够 i 匹配上等价于一个对 i,i+1,......,i+len-1 的限制，用 bitset 的左移右移得到这些限制，然后我把这些限制取 and，这个时候如果还是 1 的话就说明能过匹配上，我们只需要求出来区间 1 的个数即可。

时间复杂度 O(\frac {nm|\sum|}w+\frac{nl}w)，其中 m 是插入和删除的操作次数，l 是查询串的长度之和。

const int N=1e6+5,inf=1e9+7;
int n,q,T; string p;
bitset<N> f[10],t;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>q;
    while(q--){
        int o,x,y;
        cin>>o;
        if(o==0){
            cin>>x>>p;
            for(int i=0;i<10;i++)t=(f[i]>>x)<<x,f[i]^=t,f[i]|=t<<(p.size());
            for(int i=0;i<p.size();i++)f[p[i]-'0'][i+x]=1;
        }
        if(o==1){
            cin>>x>>y;
            for(int i=0;i<10;i++)t=(f[i]>>x)<<x,f[i]^=t,t=(t>>y)<<x,f[i]|=t;
        }
        if(o==2){
            cin>>x>>y>>p;
            if(p.size()>y-x){printf("0\n");continue;}
            t.set();
            for(int i=0;i<p.size();i++)t&=(f[p[i]-'0']>>i);
            printf("%d\n",(t>>x).count()-(t>>(y-p.size()+1)).count()); 
        }
    }
    return 0;
}