Croc Champ 2013 - Qualification Round : E. Tree-String Problem

本番にTLEで解けなかった問題にチャレンジ。
http://codeforces.com/contest/291/problem/E

問題

ある点を根とする木構造が与えられる。
また、木構造の各辺には文字列が与えられている。

最後に、目的の文字列が与えられる。
根から葉にたどっていった時に、目的の文字列が登場する総数を求めよ。

解法

基本的には辺を辿るたびに、その辺の文字列をそこまでの文字列の接尾辞として連結し、目的の文字列が含まれるか答える。

ここで、今さらながら自分が高速な文字列検索手法を知らないことに気づいた。
各辺の文字列と目的の文字列の長さの和は最大30万。
何も考えず単純に検索すると、辺の文字列長Nと目的の文字列長Mに対しO(NM)かかるので時間切れする。

そこで、文字列検索アルゴリズムを少し勉強。
ローリングハッシュを使うラビンカープ法とKMP法を実装してみた。

ただ、前者は、ハッシュ値が一致しても最終的な文字列一致検索でO(NM)かかるのでアウト。
前者でハッシュ値だけで判定して文字列一致を省略するか、もしくはKMP法ならOK。

なお、最初KMP法を行う際にstring.c_str()を大量に実行してchar*にしたらタイムアウトした。
c_str()は不要に連発するもんじゃないな…。

int N;
vector<int> E[100001];
string P[100001];
int L[100001];
string T;
ll TH,THL;
char buf[400005];
char Ts[400005];
ll mo=1000000007;

ll dfs(int cur, int TL,ll hash) {
	ll res=0;
	int i,x;
	int NL=TL+P[cur].size();
	
	strcpy(buf+TL,P[cur].c_str());
	FOR(i,P[cur].size()) {
		hash=(hash*256+buf[TL+i]) % mo;
		if(TL+i>=T.size()) hash=(((hash-THL*buf[TL+i-T.size()])%mo)+mo)%mo;
		
		if(hash==TH && TL+i+1>=T.size()) res++;
	}
	
	FOR(i,E[cur].size()){
		res += dfs(E[cur][i],NL,hash);
		buf[NL]=0;
	}
	
	return res;
	
}

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	N=GETi();
	FOR(i,N-1) {
		cin >> j >> P[i+2];
		E[j].push_back(i+2);
	}
	cin >> T;
	strcpy(Ts,T.c_str());
	TH=0;
	THL=1;
	FOR(i,T.size()){
		TH=(TH*256+T[i]) % mo;
		THL=(THL*256) % mo;
	}
	
	cout << dfs(1,0,0) << endl;
	
	return;
}

int N;
vector<int> E[100001];
string P[100001];
string T;

int KMPT[4*100000];
ll res;

void KMPproc(int c){
	res++;
}

int KMP(string& tar,string& pat, int cur=0) {
	int c,p=0,l,pl;
	
	FOR(c,tar.size()) {
		while(cur>-1 && pat[cur]!=tar[c]) cur=KMPT[cur];
		if(++cur >= pat.size()) {
			KMPproc(c);
			cur=KMPT[cur];
		}
	}
	return cur;
}

void prepKMP(string& str) {
	int i,n;
	
	n=KMPT[0]=-1;
	FOR(i,str.size()) {
		while(n>-1 && str[i]!=str[n]) n=KMPT[n];
		n++;
		KMPT[i+1]=(str[i+1]==str[n])?KMPT[n]:n;
	}
}


ll dfs(int cur, int state) {
	int i;
	
	state = KMP(P[cur], T, state);
	FOR(i,E[cur].size()) dfs(E[cur][i],state);
	
	return res;
	
}

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	N=GETi();
	FOR(i,N-1) {
		cin >> j >> P[i+2];
		E[j].push_back(i+2);
	}
	cin >> T;
	prepKMP(T);
	res=0;
	dfs(1,0);
	cout << res << endl;
	
	return;
}

まとめ

文字列一致検索のアルゴリズムを知らなかったのは勉強不足として、c_str()が重いのは誤算だった。
c_strやめるだけで数倍速くなった…。