結果

問題 No.2761 Substitute and Search
コンテスト
ユーザー nonon
提出日時 2024-05-18 08:02:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,847 ms / 4,000 ms
コード長 2,538 bytes
コンパイル時間 2,288 ms
コンパイル使用メモリ 207,356 KB
最終ジャッジ日時 2025-02-21 15:41:09
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace std;
using namespace atcoder;
using ull=unsigned long long;
const ull mod=(1ULL<<61)-1;
ull op(ull a, ull b){return (a+b)%mod;}
ull e(){return 0;}
struct rolling_hash
{
    int _n=3030;
    segtree<ull,op,e>seg=segtree<ull,op,e>(_n);
    rolling_hash()=default;
    rolling_hash(string s, ull b):S(s),base(b)
    {
        int n=S.size();
        assert(n<_n);
        for(int i=0;i<n;i++){
            if(i==0)base_pow[0]=1;
            else base_pow[i]=mul(base,base_pow[i-1]);
            seg.set(i,mul(ull(S[i]),base_pow[i]));
        }
    }
    void set(int i, char c)
    {
        S[i]=c;
        seg.set(i,mul(ull(S[i]),base_pow[i]));
    }
    ull hash(int l, int r)
    {
        return mul(seg.prod(l,r),pow(base_pow[l],mod-2));
    }
    ull all_hash()
    {
        return hash(0,S.size());
    }
private:
    string S;
    ull base;
    const ull mask30=(1ULL<<30)-1;
    const ull mask31=(1ULL<<31)-1;
    vector<ull>base_pow=vector<ull>(_n);
    ull mul(ull a, ull b)
    {
        ull au=a>>31,ad=a&mask31;
        ull bu=b>>31,bd=b&mask31;
        ull m=ad*bu+au*bd;
        ull mu=m>>30,md=m&mask30;
        return calc_mod(2*au*bu+mu+(md<<31)+ad*bd);
    }
    ull calc_mod(ull v)
    {
        ull vu=v>>61,vd=v&mod;
        ull res=vu+vd;
        if(res>=mod)res-=mod;
        return res;
    }
    ull pow(ull a, ull n)
    {
        ull res=1;
        while(n)
        {
            if(n&1)res=mul(res,a);
            a=mul(a,a);
            n/=2;
        }
        return res%mod;
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(NULL));
    const int base=rand()%100000+1;
    int N,L,Q;
    cin>>N>>L>>Q;
    vector<string>S(N);
    for(int i=0;i<N;i++)cin>>S[i];
    vector<rolling_hash>RH;
    for(int i=0;i<N;i++)RH.push_back(rolling_hash(S[i],base));
    while(Q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int p;
            char C,D;
            cin>>p>>C>>D;
            p--;
            for(int i=0;i<N;i++)if(S[i][p]==C)
            {
                S[i][p]=D;
                RH[i].set(p,D);
            }
        }
        else
        {
            string T;
            cin>>T;
            ull hashT=rolling_hash(T,base).all_hash();
            int ans=0;
            for(int i=0;i<N;i++)
            {
                ull hashS=RH[i].hash(0,T.size());
                if(hashT==hashS)ans++;
            }
            cout<<ans<<'\n';
        }
    }
}
0