kmjp's blog

競技プログラミング参加記です

Codeforces ECR #016 : F. String Set Queries

これは勉強になった。
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の記事もすんなり読めるようになる。