Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- using namespace std;
- const int maxn = 300300;
- vector<int> g[maxn];
- string s[maxn];
- int m;
- char t[maxn];
- int c[maxn];
- int top = 0;
- int ans = 0;
- void calc(char sym) {
- int j = c[top - 1];
- while (j > 0 && sym != t[j])
- j = c[j - 1];
- if (sym == t[j]) ++j;
- c[top++] = j;
- }
- void dfs(int u) {
- for(size_t i = 0; i < g[u].size(); ++i) {
- int v = g[u][i];
- for(int j = 0; j < s[v].size(); ++j) {
- calc(s[v][j]);
- if(c[top - 1] == m) {
- ++ans;
- }
- }
- dfs(v);
- top -= s[v].size();
- }
- }
- int main(int argc, char **argv) {
- int n;
- scanf("%d", &n);
- for(int i = 1; i < n; ++i) {
- int p;
- scanf("%d %s", &p, t);
- --p;
- s[i] = t;
- g[p].push_back(i);
- }
- scanf("\n%s", t);
- m = strlen(t);
- c[top++] = 0;
- for(int i = 1; i < m; ++i) {
- calc(t[i]);
- }
- calc('#');
- dfs(0);
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement