Codeforces 291E Tree String Problem

Codeforces 文字列

問題

辺に文字列のついた根付き木が与えられる。
この木から文字列を以下のようにして作ることができる。

  • 始点の(枝，枝の文字の何番目か）、終点の（枝，枝の文字の何番目か）を選ぶ。
  • 必ず始点のほうが根に近いほうを選ぶものとする。
  • 始点枝から終点の枝まで木の枝を辿っていって、間にあった文字列をすべてつなげる。

始点の枝、終点の枝の選んだ文字より外側にある文字は入れない。
詳しくは問題の図を参照。


できた文字列が与えられるとき、その文字列を作るような始点、終点のペアは何通り考えられるか、求めよ。

制約条件

頂点≦10^5
入力の文字列の文字数の合計は3*10^5を超えない

方針

KMPでfailure linkを作る。
作ったら、根から、(今どのノードにいるか、最大何文字マッチできるか）を状態としてDFSすればよい。


一つの枝でも、開始点を複数選べる場合がある
（出来上がりの文字列がabababcで、枝がababの場合、0文字目か2文字目どちらでもスタートできる）
ため、最大マッチの文字数だけをもってよいのか不安になるが、
最大でi文字マッチをしているということは、i文字の途中までもマッチしているという情報を持っているので大丈夫になっている。


abababだったら、6文字目までマッチしていたら、同じ個数だけ2文字マッチ、4文字マッチの状態があるが、それは「6文字目までマッチ」という情報から過不足なくわかるという意味。
一回マッチしたら、KMPのfailure linkで、できるだけマッチが減らないように戻るから。abababで6文字目で終了した場合、次はababまで戻ってもう一回マッチが始まるので、2文字遅れてマッチが始まっている場合もきちんとカバーされている。

ソースコード

int n, *fail;
string in[100010];
vector<vi> e;

int *buildFail(const char *p) {
  int m = strlen(p);
  int *fail = new int[m+1];
  int j = fail[0] = -1;
  for (int i = 1; i <= m; ++i) {
    while (j >= 0 && p[j] != p[i-1]) j = fail[j];
    fail[i] = ++j;
  }
  return fail;
}
ll rec(int c, int p){
	ll res = 0;
	rep(i, e[c].size()){
		int t = p;
		rep(j, in[e[c][i]].size()){
			while(t >= 0 && in[e[c][i]][j] != in[0][t]) t = fail[t];
			if(++t == in[0].size()){
				res++;
				t = fail[t];
			}
		}
		res += rec(e[c][i], t);
	}
	return res;
}
int main(){
	
	cin >> n;
	e.resize(n);
	for(int i = 1; i < n; i++){
		int p;
		cin >> p;
		p--;
		e[p].pb(i);
		cin >> in[i];
	}
	cin >> in[0];
	
	fail = buildFail(in[0].c_str());
	cout << rec(0, 0) << endl;
	
	return 0;
}