結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
![]() |
提出日時 | 2024-05-17 21:52:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,592 ms / 4,000 ms |
コード長 | 2,644 bytes |
コンパイル時間 | 4,512 ms |
コンパイル使用メモリ | 260,388 KB |
最終ジャッジ日時 | 2025-02-21 14:44:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 struct rolling_hash{ long long t_hash; static inline vector<long long> power; static const long long MOD = (1LL<<61)-1; static const long long b = 123456; int sz; rolling_hash(){ sz = 0; t_hash = 0; } rolling_hash(char c){ sz = 1; t_hash = b*c; } long long mul(__int128 x,__int128 y){ __int128 t = x*y; t = (t>>61) + (t&MOD); if(t>=MOD)t -= MOD; return t; } long long get_pow(int sz){ if(power.size()>sz)return power[sz]; while(power.size()<=sz){ if(power.size()==0)power.push_back(1); else power.push_back(mul(power.back(),b)); } return power.back(); } rolling_hash &operator+=(const rolling_hash &another){ (*this).t_hash = mul((*this).t_hash,get_pow(another.sz)); (*this).t_hash += another.t_hash; if((*this).t_hash>=MOD)(*this).t_hash -= MOD; (*this).sz += another.sz; return (*this); } rolling_hash operator+(const rolling_hash &another)const{ return (rolling_hash(*this)+=another); } rolling_hash &operator-=(const rolling_hash &another){ (*this).t_hash += MOD - mul(another.t_hash,get_pow((*this).sz-another.sz)); if((*this).t_hash>=MOD)(*this).t_hash -= MOD; (*this).sz -= another.sz; return (*this); } rolling_hash operator-(const rolling_hash &another)const{ return (rolling_hash(*this)-=another); } bool operator<(const rolling_hash &another)const{ if((*this).t_hash!=another.t_hash)return (*this).t_hash<another.t_hash; return (*this).sz<another.sz; } bool operator==(const rolling_hash &another)const{ return ((*this).t_hash==another.t_hash && (*this).sz==another.sz); } }; rolling_hash op(rolling_hash a,rolling_hash b){ return a+b; } rolling_hash e(){ return rolling_hash(); } int main(){ int N,L,Q; cin>>N>>L>>Q; vector<segtree<rolling_hash,op,e>> seg(N); rep(i,N){ string s; cin>>s; vector<rolling_hash> v(s.size()); rep(j,L){ v[j] = rolling_hash(s[j]); } seg[i] = segtree<rolling_hash,op,e>(v); } rep(_,Q){ int t; cin>>t; if(t==1){ int k; char c,d; cin>>k>>c>>d; k--; rep(i,N){ if(seg[i].get(k)==rolling_hash(c)){ seg[i].set(k,rolling_hash(d)); } } } else{ int ans = 0; string t; cin>>t; rolling_hash H; rep(j,t.size()){ H += rolling_hash(t[j]); } rep(i,N){ if(seg[i].prod(0,t.size())==H)ans++; } cout<<ans<<endl; } } return 0; }