AC自动机——病毒侵袭 ( HDU 2896 )

  • 题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=2896

  • 分析:

给出N个子串建树,再给出M个母串来查询每个母串含有哪几个子串。还是一只自动AC机~

  • 题解:

直接套用AC自动机模板,不过需要修改几个地方:

建树:

1void insert(char *s) 2{ 3 Node * t = root; 4 for(;*s;s++) 5 { 6 int x = *s ; 7 if(t -> ch[x] == NULL) 8 t -> ch[x] = newNode(); 9 t = t -> ch[x]; 10 } 11 t -> match = loc++;//开一个全局变量loc存储病毒的编号,每存储一个病毒,编号递增一下。 12} 13

匹配:

1 bool run(char *s) //判断每个网站有没有含病毒,并记录病毒编号 2 { 3 CLR(ans); 4 bool flag = false; 5 Node * t = root; 6 for(; *s ; s++) 7 { 8 int x = *s ; 9 t = t->ch[x]; 10 for(Node*u = t; u->match != -1;u = u->fail) 11 { 12 if(u->match>0)//match大于0表示匹配完成了一个病毒 13 { 14 int tmp = u->match; 15 if(!ans[tmp]) //如果ans数组里没有存储该病毒 16 { 17 ans[tmp] = 1;//存储病毒 18 cnt++; //该网站含病毒数++ 19 } 20 flag = true; //表示该网站含有病毒 21 } 22 } 23 } 24 return flag; 25 } 26
  • AC代码:

1#include <cstdio> 2#include <iostream> 3#include <cstdlib> 4#include <cstring> 5#include <algorithm> 6#include <cmath> 7#include <cctype> 8#include <map> 9#include <set> 10#include <queue> 11using namespace std; 12typedef pair<int,int> Pii; 13typedef long long LL; 14typedef unsigned long long ULL; 15typedef double DBL; 16typedef long double LDBL; 17#define MST(a,b) memset(a,b,sizeof(a)) 18#define CLR(a) MST(a,0) 19#define Sqr(a) ((a)*(a)) 20 21 22int loc; 23int cnt; 24const int k = 128; 25const int MAXN = 60010; 26int ans[MAXN]; 27struct Node 28{ 29 Node* ch[k], *fail; 30 int match; 31 void clear() 32 { 33 memset(this, 0, sizeof(Node)); 34 } 35}; 36Node * que[MAXN]; 37struct ACAutomaton 38{ 39 Node nodes[MAXN], *root, *superRoot, *cur; //全局变量 40 Node * newNode() //从内存池中初始化一个结点 41 { 42 cur -> clear(); 43 return cur++; 44 } 45 void clear() //清空整个字典树 46 { 47 cur = nodes; 48 superRoot = newNode(); 49 root = newNode(); 50 root -> fail = superRoot; 51 for(int i=0;i<k;i++) //superRoot为虚拟的超级根结点,所有孩子均指向实际的根结点,减少建立自动机的代码量 52 superRoot -> ch[i] = root; 53 superRoot->match = -1; 54 } 55 void insert(char *s) 56 { 57 Node * t = root; 58 for(;*s;s++) 59 { 60 int x = *s ; 61 if(t -> ch[x] == NULL) 62 t -> ch[x] = newNode(); 63 t = t -> ch[x]; 64 } 65 t -> match = loc++; 66 } 67 void build() //使用自动机前,要先生成失配指针 68 { 69 int p=0, q =0; 70 que[q++] = root; 71 while(p!=q) //BFS求失配指针 72 { 73 Node*t = que[p++]; 74 for(int i=0;i<k;i++) 75 { 76 if(t->ch[i]) 77 { 78 t -> ch[i] -> fail = t->fail ->ch[i]; 79 que[q++] = t->ch[i]; 80 }else 81 t->ch[i] = t -> fail ->ch[i]; 82 83 } 84 } 85 } 86 87 bool run(char *s) //在自动机上与匹配串s进行匹配 88 { 89 CLR(ans); 90 bool flag = false; 91 Node * t = root; 92 for(; *s ; s++) 93 { 94 int x = *s ; 95 t = t->ch[x]; 96 for(Node*u = t; u->match != -1;u = u->fail) 97 { 98 if(u->match>0) 99 { 100 int tmp = u->match; 101 if(!ans[tmp]) 102 { 103 ans[tmp] = 1; 104 cnt++; 105 } 106 flag = true; 107 } 108 //u -> match = -1; 109 } 110 } 111 return flag; 112 } 113 114}; 115 116int n; 117ACAutomaton j; 118char s[20000]; 119 120int main() 121{ 122 123 int N,M; 124 while(~scanf("%d", &N)) 125 { 126 j.clear(); 127 loc = 1; 128 int n = N; 129 while(n--) 130 { 131 scanf("%s", s); 132 j.insert(s); 133 } 134 j.build(); 135 scanf("%d", &M); 136 int total = 0; 137 int i =1; 138 while(M--) 139 { 140 cnt = 0; 141 scanf("%s", s); 142 bool flag = j.run(s); 143 if(flag) 144 { 145 //cout << cnt << endl; 146 sort(ans, ans+cnt); 147 total++; 148 printf("web %d: ", i); 149 for(int j=1;j<=N;j++) 150 { 151 if(ans[j] == 1) 152 { 153 cout << j; 154 cnt--; 155 if(cnt) cout << " "; 156 else 157 { 158 cout << endl; 159 break; 160 } 161 } 162 } 163 } 164 i++; 165 } 166 printf("total: %d\n", total); 167 } 168 return 0; 169} 170 171

代码交流 2021