fork(2) download
copy 
  1. //NOI2011(BZOJ2434); 阿狸的打字机; AC Automation - Fail Tree & Binary Indexed Tree
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #define N 100000
  6.  
  7. struct edge
  8. {
  9.     int next, node;
  10. };
  11. struct map
  12. {
  13.     int head[N + 1], tot;
  14.     edge e[N + 1];
  15.     map() { tot = 0; }
  16.     inline void addedge(int x, int y)
  17.     {
  18.         e[++tot].next = head[x];
  19.         e[tot].node = y;
  20.         head[x] = tot;
  21.     }
  22. }fail, queries;
  23. //Forward stars, one for fail pointer tree and one for queries
  24. const int root = 1;
  25. struct node
  26. {
  27.     int f, son[26], fail;
  28. }t[N + 1];
  29. //Trie tree
  30. char s[N + 1];
  31. //Entry string
  32. int len, tot = root, strs = 0, m;
  33. int strNode[N + 1];
  34. //Corresponding trie node for a string
  35. int queue[N + 1];
  36. int head[N + 1], tail[N + 1], count = 0;
  37. //DFS sequence
  38. int arr[N + 1];
  39. //Binary indexed tree, storing how many nodes of string y are in a certain node and its subtrees
  40. int ans[N + 1];
  41. //Stores the answer to each of the queries
  42.  
  43. inline int query(int x)
  44. {
  45.     int ret = 0;
  46.     for (; x; x -= x & (-x))
  47.         ret += arr[x];
  48.     return ret;
  49. }
  50.  
  51. inline void modify(int x, int d)
  52. {
  53.     for (; x <= count; x += x & (-x))
  54.         arr[x] += d;
  55. }
  56.  
  57. void dfs(int x)
  58. {
  59.     head[x] = ++count;
  60.     for (int i = fail.head[x]; i; i = fail.e[i].next)
  61.         dfs(fail.e[i].node);
  62.     tail[x] = count;
  63. }
  64.  
  65. int main()
  66. {
  67.     gets(s);
  68.     len = strlen(s);
  69.     int now = root;
  70.     //Read queries and build queries graph
  71.     scanf("%d", &m);
  72.     for (int x, y, i = 0; i < m; ++i)
  73.     {
  74.         scanf("%d%d", &x, &y);
  75.         queries.addedge(y, x);
  76.     }
  77.     //Build trie tree
  78.     for (int i = 0; i < len; ++i)
  79.     {
  80.         if (s[i] == 'P') strNode[++strs] = now;
  81.         else if (s[i] == 'B') now = t[now].f;
  82.         else
  83.         {
  84.             if (t[now].son[s[i] - 'a']) now = t[now].son[s[i] - 'a'];
  85.             else
  86.             {
  87.                 int cur = now;
  88.                 t[now = t[now].son[s[i] - 'a'] = ++tot].f = cur;
  89.             }
  90.         }
  91.     }
  92.     //Construct fail pointers and build fail pointer tree
  93.     int l = 0, r = -1;
  94.     for (int i = 0; i < 26; ++i)
  95.     {
  96.         if (t[root].son[i])
  97.         {
  98.             queue[++r] = t[root].son[i];
  99.             fail.addedge(root, queue[r]);
  100.             t[queue[r]].fail = root;
  101.         }
  102.     }
  103.     for (; l <= r; ++l)
  104.     {
  105.         for (int i = 0; i < 26; ++i)
  106.             if (t[queue[l]].son[i])
  107.             {
  108.                 queue[++r] = t[queue[l]].son[i];
  109.                 for (now = t[queue[l]].fail; now != root && !t[now].son[i]; now = t[now].fail) ;
  110.                 t[queue[r]].fail = t[now].son[i] ? t[now].son[i] : root;
  111.                 fail.addedge(t[queue[r]].fail, queue[r]);
  112.             }
  113.     }
  114.     //Construct DFS sequence of fail pointer tree
  115.     dfs(root);
  116.     //Traverse through trie tree while enumerating y string
  117.     now = root, strs = 0;
  118.     for (int qs, i = 0; i < len; ++i)
  119.     {
  120.         if (s[i] == 'B')
  121.         {
  122.             modify(head[now], -1);
  123.             now = t[now].f;
  124.         }
  125.         else if (s[i] != 'P')
  126.         {
  127.             now = t[now].son[s[i] - 'a'];
  128.             modify(head[now], 1);
  129.         }
  130.         else
  131.         {
  132.             for (int x = queries.head[++strs]; x; x = queries.e[x].next)
  133.                 ans[x] = query(tail[strNode[queries.e[x].node]]) - query(head[strNode[queries.e[x].node]] - 1);
  134.         }
  135.     }
  136.     for (int i = 1; i <= m; ++i)
  137.         printf("%d\n", ans[i]);
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0.01s 18408KB
comments (?)
stdin
copy 
aPaPBbP
3
1 2
1 3
2 3
stdout
copy 
2
1
0
https://ideone.com/u6QNJ
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!