これは勉強になった。
http://codeforces.com/contest/710/problem/F
問題
以下のクエリを処理せよ。
ただし3つ目の質問クエリはその都度回答しないと、次のクエリは与えられない(先読みは出来ない)。
- 入力文字列sを文字列集合Dに追加する
- 入力文字列sを文字列集合Dから削除する(先にDにsが入っていることは保証される)
- 文字列Sが与えられるので、部分文字列としてD中の文字列が登場する回数を答えよ
解法
追加クエリで与えられた文字列集合をA、削除クエリで与えられた文字列集合をBとする。
3つ目のクエリは、Sに対しA中の文字列の登場回数からB中の文字列の登場回数を引き算すればいいので、実質追加クエリと削除クエリはやることが一緒である。
よって後は3つ目のクエリの解き方を考えよう。
基本的にはAho-Corasick法である。ただ、文字列集合が徐々に増加し、その都度AC法の状態遷移図を作っているとTLEする。
そこで、AC法の状態遷移図の書き換えを抑える方法を考える。
これには以下の記事が参考になる。
Decomposable searching problem Wiki - yukicoder
今、n個の文字列集合に対するAC法の状態遷移図を考える。
その際、nを2進数表記し、1がたったビットに対応する文字列群でそれぞれAC法の遷移図を作ろう。
例えばn=27=11011bであれば、先頭16個、次8個、次2個、最後1個の文字列でそれぞれAC法の状態遷移図を作ろう。
こうして作る状態遷移図はO(log n)個で済む。
質問クエリについては、それぞれの状態遷移図を用いてAC法を適用すればよい。
ここで、1つめのクエリによりn=28=11100bとなったとする。
この場合、新たに1が立ったビットに対応する文字列群、今回の場合最後の4文字列のみでAC法の状態遷移図を作る。
この要領でAC法の状態遷移図を作り変えていく場合、各文字列はO(log n)回しか対象とならないため、愚直に毎回状態遷移図を全部再生成するよりずっと軽量で済む。
const int NUMC=26; class Trie { public: vector<vector<int> > V; int find(string s) { int cur=0; ITR(it,s) if((cur=V[cur][*it+1])==0) return -1; return cur; } void create(vector<string> S) { // 0 is for backtrack V.clear(); V.push_back(vector<int>(NUMC+1)); sort(S.begin(),S.end()); ITR(it,S) { int cur=0; ITR(c,(*it)) { if(V[cur][*c+1]==0) V.push_back(vector<int>(NUMC+1)),V[cur][*c+1]=V.size()-1; cur=V[cur][*c+1]; } } } }; class ACmatch_num { public: Trie t; vector<int> acc; int ma; void create(vector<string> S) { int i; ma=S.size(); t.create(S); acc.clear(); acc.resize(t.V.size()); FOR(i,S.size()) acc[t.find(S[i])]++; queue<int> Q; FOR(i,NUMC) if(t.V[0][i+1]) t.V[t.V[0][i+1]][0]=0, Q.push(t.V[0][i+1]); while(!Q.empty()) { int k=Q.front(); Q.pop(); FOR(i,NUMC) if(t.V[k][i+1]) { Q.push(t.V[k][i+1]); int pre=t.V[k][0]; while(pre && t.V[pre][i+1]==0) pre=t.V[pre][0]; t.V[t.V[k][i+1]][0]=t.V[pre][i+1]; acc[t.V[k][i+1]] += acc[t.V[pre][i+1]]; } } } int match(string S) { int R=0; int cur=0; ITR(it,S) { while(cur && t.V[cur][*it+1]==0) cur=t.V[cur][0]; cur=t.V[cur][*it+1]; R+=acc[cur]; } return R; } }; int M; vector<string> V[2]; ACmatch_num acm[2][20]; void build(int id,string s) { V[id].push_back(s); int cn=V[id].size(), pn=V[id].size()-1, tot=0; int i,j; for(i=19;i>=0;i--) if(cn&(1<<i)) { if((pn&(1<<i))==0) { vector<string> S; FOR(j,1<<i) S.push_back(V[id][tot+j]); acm[id][i].create(S); } tot+=1<<i; } } void solve() { int i,j,k,l,r,x,y; string s; cin>>M; while(M--) { cin>>i>>s; FORR(c,s) c-='a'; if(i<=2) build(i-1,s); else { ll ret=0; for(i=19;i>=0;i--) { if(V[0].size()&(1<<i)) ret+=acm[0][i].match(s); if(V[1].size()&(1<<i)) ret-=acm[1][i].match(s); } cout<<ret<<endl; } } }
まとめ
yukicoderの記事は一見難しく見えるけど、先にこの問題のEditorialを見て解いておくと、yukicoderの記事もすんなり読めるようになる。