P4465 [国家集训队] JZPSTR

int_R · 2023-10-09 17:01:10 · 题解

P4465 [国家集训队] JZPSTR

更好的阅读体验

莪怺逺禧歡仳特噻特。

5k 爷很早以前就让我写这个 bitset 水题。

在一个字符串中插入字符串，删除字符串，查询给定子串出现次数。

插入，删除，字符集大小小，z_i 总长度小。这不妥妥 bitset！

关于 bitset 匹配：

我们对于每一种字符 c 开一个 bitset b_c，然后将 b_{s_i} 的第 i 位设置为 1，也就是对于每种字符记录出它在 s 中所有的出现位置。

对于一个字符串 t，与 s 进行字符串匹配。我们开一个记录答案的 bitset ans，意义是每一个为 1 的位都是 t 在 s 中的起始位置(有些写法是结束位置)。初始时将 ans 每一位都赋值为 1。举个例子：

我们遍历 t 的每一位，使 ans\gets ans\operatorname{bitand} (b_{y_i}\operatorname{>>}i)（字符串向左移，但是 bitset 中是右移）。

最后得到的就是所有起始位置，匹配的时间复杂度是 O(\dfrac{|s|\sum |t_i|}{\omega})。

回到这道题上，查询操作已经迎刃而解，插入删除怎么做？多运用位运算思想。

我们定义一个全 1 的 bitest k。

提取出 b 的第 x 位及以后可以表示为 b&(k<<x)，那同理提取出 b 的第 x 位以前就可以表示为 b&(~(k<<x))。

那么对于每个 b_c。

对于插入操作，提取出 x 位及以后，左移 |t| 位，或上 x 位以前，插入的部分正常遍历处理一遍。

对于删除操作，提取出 y 位及以后，右移 y-x 位，或上 x 位以前。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
using namespace std;
const int MAXN=1e6+10;
int q,n;bitset <MAXN> b[10],ans,k,r;
int main()
{
#ifdef ONLINE_JUDGE
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>q;
    while(q--)
    {
        int opt;cin>>opt;k.set();
        if(!opt)
        {
            int x;string t;cin>>x>>t;r=~(k<<x);
            for(register int i=0;i<=9;++i)
                b[i]=((b[i]&(k<<x))<<t.size())|(b[i]&r);
            for(register int i=0;i<t.size();++i)
                b[t[i]-'0'].set(x+i);
        }
        if(opt==1)
        {
            int x,y;cin>>x>>y;r=~(k<<x);
            for(register int i=0;i<=9;++i)
                b[i]=((b[i]&(k<<y))>>(y-x))|(b[i]&r);
        }
        if(opt==2)
        {
            int x,y;string t;cin>>x>>y>>t;ans.set();
            for(register int i=0;i<t.size();++i) ans&=b[t[i]-'0']>>i;
            if(y-x<t.size()) cout<<"0\n";
            else cout<<(ans>>x).count()-(ans>>y-t.size()+1).count()<<'\n';
        }
    }
    return 0;
}