Advertisement
Guest User

Untitled

a guest
Apr 14th, 2013
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. const int maxn = 300300;
  10.  
  11. vector<int> g[maxn];
  12. string s[maxn];
  13. int m;
  14. char t[maxn];
  15. int c[maxn];
  16. int top = 0;
  17. int ans = 0;
  18.  
  19. void calc(char sym) {
  20.     int j = c[top - 1];
  21.     while (j > 0 && sym != t[j])
  22.         j = c[j - 1];
  23.     if (sym == t[j])  ++j;
  24.     c[top++] = j;
  25. }
  26.  
  27. void dfs(int u) {
  28.     for(size_t i = 0; i < g[u].size(); ++i) {
  29.         int v = g[u][i];
  30.         for(int j = 0; j < s[v].size(); ++j) {
  31.             calc(s[v][j]);
  32.             if(c[top - 1] == m) {
  33.                 ++ans;
  34.             }
  35.         }
  36.         dfs(v);
  37.         top -= s[v].size();
  38.     }
  39. }
  40.  
  41. int main(int argc, char **argv) {
  42.     int n;
  43.     scanf("%d", &n);
  44.     for(int i = 1; i < n; ++i) {
  45.         int p;
  46.         scanf("%d %s", &p, t);
  47.         --p;
  48.         s[i] = t;
  49.         g[p].push_back(i);
  50.     }
  51.     scanf("\n%s", t);
  52.     m = strlen(t);
  53.     c[top++] = 0;
  54.     for(int i = 1; i < m; ++i) {
  55.         calc(t[i]);
  56.     }
  57.     calc('#');
  58.     dfs(0);
  59.     cout << ans << endl;
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement