Advertisement
Lexolordan

Untitled

Nov 11th, 2018
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <unordered_map>
  5.  
  6. using namespace std;
  7.  
  8. struct Tree {
  9.     int flag;
  10.     Tree* next[26], *go[26];
  11.     Tree *parent, *link;
  12.     char ch;
  13.  
  14.     Tree(char ch, Tree *parent) : ch(ch), parent(parent), flag(0), link(0) {
  15.         for (int i = 0; i < 26; ++i) {
  16.             next[i] = NULL;
  17.             go[i] = NULL;
  18.         }
  19.     }
  20. };
  21.  
  22. Tree *root = new Tree(0, 0);
  23. Tree *go(Tree *v, char c);
  24.  
  25. void add(Tree *root, string s) {
  26.     for (char c : s) {
  27.         auto it = root->next[c - 'a'];
  28.  
  29.         if (it != NULL) {
  30.             root = it;
  31.         } else {
  32.             Tree *v = new Tree(c, root);
  33.  
  34.             root->next[c - 'a'] = v;
  35.             root = v;
  36.         }
  37.     }
  38.  
  39.     root->flag++;
  40. }
  41.  
  42. Tree *link(Tree *v) {
  43.     if (!v->link) {
  44.         if (v->parent == root || v == root)  {
  45.             v->link = root;
  46.         } else {
  47.             v->link = go(link(v->parent), v->ch);
  48.         }
  49.     }
  50.  
  51.     return v->link;
  52. }
  53.  
  54. Tree *go(Tree *v, char c) {
  55.     if (v->go[c - 'a'] == NULL) {
  56.         if (v->next[c - 'a'] != NULL) {
  57.             v->go[c - 'a'] = v->next[c - 'a'];
  58.         } else {
  59.             v->go[c - 'a'] = (v == root ? root : go(link(v), c));
  60.         }
  61.     }
  62.  
  63.     return v->go[c - 'a'];
  64. }
  65.  
  66. unordered_map<Tree*, int> is_term;
  67. int is_terminal(Tree *v) {
  68.     if (v == root) {
  69.         return 0;
  70.     }
  71.  
  72.     if (is_term.find(v) == is_term.end()) {
  73.         is_term[v] = (v->flag + is_terminal(link(v)));
  74.     }
  75.  
  76.     return is_term[v];
  77. }
  78.  
  79. vector<pair<int, char>> g[(int)1e5];
  80.  
  81. long long ans = 0;
  82. unordered_map<Tree*, int> been;
  83. void dfs(int v, Tree *now) {
  84.     ans += (long long)is_terminal(now);
  85.  
  86.     for (auto x : g[v]) {
  87.         dfs(x.first, go(now, x.second));
  88.     }
  89. }
  90.  
  91. int main() {
  92.     int n;
  93.     cin >> n;
  94.  
  95.     for (int i = 0; i < n; ++i) {
  96.         int k;
  97.         cin >> k;
  98.         for (int j = 0; j < k; ++j) {
  99.             int to;
  100.             char c;
  101.             cin >> to >> c;
  102.             to--;
  103.  
  104.             g[i].push_back({to, c});
  105.         }
  106.     }
  107.     cin >> n;
  108.  
  109.     string s;
  110.     for (int i = 0; i < n; ++i) {
  111.         cin >> s;
  112.  
  113.         add(root, s);
  114.     }
  115.  
  116.     dfs(0, root);
  117.     cout << ans << endl;
  118.     return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement