Gemini Boy - ACM之路~

Codeforces 291E. Tree-String Problem

链接：http://codeforces.com/problemset/problem/291/E

题意就是说给你一棵树，边权是字符串，然后从根节点到叶子节点的所有路径中，出现模板串的个数。

做法就是dfs+kmp，对目标串得到next数组，然后从根节点dfs，一边dfs一边跑kmp进行匹配。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int maxn = 100100;

struct Edge {
	int to;
	string s;
	Edge() {}
	Edge(int too, string str) {
		to = too; s = str;
	}
};

int n, ans = 0, next[maxn];
string t;
vector<Edge> edge[maxn];

void dfs(int u, int k) {
	for (int l = 0; l < edge[u].size(); l++) {
		int v = edge[u][l].to;
		string str = edge[u][l].s;
		int tmp = k, len = edge[u][l].s.size();
		for (int i = 0, j = k; i < len; i++) {
			while (j != -1 && str[i] != t[j+1])
				j = next[j];
			if (str[i] == t[j+1]) j++;
			if (j + 1 == t.size()) {
				j = next[j]; ans++;
			}
			tmp = j;
		}
		dfs(v, tmp);
	}
}

void work() {
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int p;
		string str;
		cin >> p >> str;
		edge[p].push_back(Edge(i, str));
	}
	cin >> t;
	next[0] = -1;
	for (int i = 1, j = -1; i < t.size(); i++) {
		while (j != -1 && t[j+1] != t[i])
			j = next[j];
		if (t[j+1] == t[i]) {
			next[i] = j + 1; j++;
		} else {
			next[i] = -1;
		}
	}
	dfs(1, -1);
	cout << ans << endl;
}

int main() {
	work();
	return 0;
}