[关闭]
@RabbitHu 2017-07-25T23:41:27.000000Z 字数 1609 阅读 1904

AC 自动机 —— WA 自动机? TLE 自动机?

笔记


名称 AC自动机
概述 Trie 树上的KMP
特点 fail 指针的处理

代码

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. using namespace std;
  7. int ncnt, n, ans;
  8. //ncnt: 数一下节点数;bcnt: 数一下模式串(B)的数目;
  9. char A[1000005], B[1000005];
  10. struct node {
  11. bool found;
  12. int id, cnt;
  13. node *fail, *nxt[26];
  14. //id: 以该节点结尾的最后一个单词
  15. //cnt: 以该节点结尾的单词数目
  16. //fail: 该节点的后缀和fail指针指向的节点后缀相同
  17. //nxt: 该节点的一个字符边指向的节点指针
  18. node(){
  19. id = cnt = found = 0;
  20. ncnt++;
  21. fail = NULL;
  22. for(int i = 0; i < 26; i++)
  23. nxt[i] = NULL;
  24. }
  25. } *root, *super_root;
  26. //root: trie树的根节点
  27. //super_root: 为了方便地处理fail指针而创建的“根节点的前缀指针”
  28. void init(){
  29. for(int i = 0; i < 26; i++)
  30. super_root -> nxt[i] = root;
  31. root -> fail = super_root;
  32. //super指针的所有字符边指向root
  33. //root的fail指针是super_root
  34. node *q[ncnt];
  35. int r;
  36. q[r = 0] = root;
  37. //用队列,bfs处理fail指针
  38. for(int l = 0; l <= r; l++){
  39. node *u = q[l];//取队首
  40. for(int i = 0; i < 26; i++){
  41. //重点!
  42. node *w = u -> nxt[i], *v = u -> fail;
  43. //w: 要构建fail指针的节点
  44. while(v -> nxt[i] == NULL) v = v -> fail;
  45. //v: 第一个有(u, w)这条边的后缀节点
  46. //如果一直到根节点都没有,v是super_root
  47. v = v -> nxt[i];
  48. //v变成了w的等效节点(w的fail)
  49. if(w != NULL)
  50. w -> fail = v, q[++r] = w;
  51. //如果w真实存在(即(u, w)边存在, 则 w的 fail 是 v,将w入队
  52. else
  53. u -> nxt[i] = v;
  54. //如果w不存在则u的这条字符边直接连向v
  55. }
  56. }
  57. }
  58. void insert(char *s){
  59. node *now = root;
  60. int l = strlen(s);
  61. for(int i = 0; i < l; i++){
  62. if(now -> nxt[s[i] - 'a'] == NULL)
  63. now -> nxt[s[i] - 'a'] = new node;
  64. now = now -> nxt[s[i] - 'a'];
  65. }
  66. now -> cnt++;
  67. }
  68. void search(char *s){
  69. node *now = root;
  70. int l = strlen(s);
  71. for(int i = 0; i < l; i++){
  72. now = now -> nxt[s[i] - 'a'];
  73. node *tmp = now; //以这个节点结尾的单词不止一个
  74. while(tmp != root){//所以这个节点的每个fail指针都要看一下
  75. if(!tmp -> found) ans += tmp -> cnt;
  76. tmp -> found = 1;
  77. tmp = tmp -> fail;
  78. }
  79. }
  80. }
  81. int main(){
  82. int T;
  83. scanf("%d", &T);
  84. while(T--){
  85. scanf("%d", &n);
  86. ans = ncnt = 0;
  87. root = new node, super_root = new node;
  88. for(int i = 1; i <= n; i++){
  89. scanf("%s", B);
  90. insert(B);
  91. }
  92. init();
  93. scanf("%s", A);
  94. search(A);
  95. printf("%d\n", ans);
  96. }
  97. return 0;
  98. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注