首页 > 代码库 > HDU 2896 病毒侵袭 AC自动机

HDU 2896 病毒侵袭 AC自动机

2024-07-14 19:01:38   223人阅读

　　刚开始学习AC自动机吧 总之WA了很多T了很多（没错 的确T了 因为在get_fail的时候很沙茶 少写了一句代码）

但是强大的gdb让我沙茶地调了半天 最终A掉这道模板题 = = （感觉还是蛮爽的）

也没考虑很多 直接上模板 然后就是WA掉之后（也不怕WA） 瞎搞调试 总之调试时很重要的

感觉有些代码累赘了——match的时候加了个flag标记 为了fail不回溯匹配已经匹配过的节点 = =  不过目的是为了“优化” （不知道是否达到效果）

另外给每一个病毒标记一下id就行 

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5 #include <string>  6 #include <algorithm>  7 #include <cstdlib>  8 #include <queue>  9 using namespace std; 10 #define INF 0x3f3f3f3f 11 #define MAXN 105 12 #define MAXM 10005 13 #define MOD 1000000007 14 #define pp(a) cout << "Debug:" << a << endl; 15 typedef long long LL; 16 typedef unsigned long long ULL; 17 typedef pair<int,int> pii; 18 struct trie { 19     int next[128]; 20     int id; 21     int fail; 22     bool flag; 23     void init() { 24         memset(next,-1,sizeof(next)); 25         id = 0; 26         fail = -1; 27         flag = 0; 28     } 29 }tree[500000]; 30 int tot;        //总数 31 void insert(char *s,int id) { 32     int len = strlen(s); 33     int now = 0; 34     for(int i = 0;i < len;i ++) { 35         int x = s[i]; 36         if(tree[now].next[x] == -1) { 37             tree[++ tot].init(); 38             tree[now].next[x] = tot; 39         } 40         now = tree[now].next[x]; 41     } 42     tree[now].id = id; 43 } 44 void get_fail() { 45     queue <int> Q; 46     Q.push(0); 47     while(!Q.empty()) { 48         int now = Q.front(); 49         Q.pop(); 50         for(int i = 0;i < 128;i ++) { 51             int x = tree[now].next[i]; 52             if(x != -1) { 53                 if(now == 0) tree[x].fail = 0; 54                 else { 55                     int p = tree[now].fail; 56                     while(p != -1) { 57                         if(tree[p].next[i] != -1) { 58                             tree[x].fail = tree[p].next[i]; 59                             break; 60                         } 61                         p = tree[p].fail; 62                     } 63                     if(p == -1) tree[x].fail = 0; 64                 } 65                 Q.push(x); 66             } 67         } 68     } 69 } 70 int ans[10]; 71 int btot,wtot; 72 void match(char *s) { 73     int len = strlen(s); 74     int p = 0; 75     for(int i = 0;i < len;i ++) { 76         int now = s[i]; 77         while(p && tree[p].next[now] == -1) p = tree[p].fail; 78         p = tree[p].next[now]; 79         if(p == -1) p = 0; 80         int tmp = p; 81         while(tmp && !tree[tmp].flag) { 82             tree[tmp].flag = 1; 83             if(tree[tmp].id) ans[btot ++] = tree[tmp].id; 84             tmp = tree[tmp].fail; 85         } 86     } 87 } 88 int main() { 89     //freopen("input.txt","r",stdin); 90     int n,m; 91     while(scanf("%d",&n) != EOF) { 92         tot = 0; 93         wtot = 0; 94         tree[tot].init(); 95         for(int i = 0;i < n;i ++) { 96             char str[205]; 97             scanf("%s",str); 98             insert(str,i + 1); 99         }100         get_fail();101         scanf("%d",&m);102         for(int i = 0;i < m;i ++) {103             //for(int j = 0;j < tot;j ++) tree[i].flag = false;104             char tmp[10005];105             btot = 0;106             scanf("%s",tmp);107             match(tmp);108             for(int j = 0;j <= tot;j ++) tree[j].flag = false;109             if(btot) {110                 sort(ans,ans + btot);111                 bool vis[10];112                 memset(vis,false,sizeof(vis));113                 for(int j = 1;j < btot;j ++) if(ans[j] == ans[j-1]) vis[j] = true;114                 printf("web %d:",i+1);115                 wtot ++;116                 for(int j = 0;j < btot;j ++) if(!vis[j]) printf(" %d",ans[j]);117                 puts("");118             }119         }120         printf("total: %d\n",wtot);121     }122     return 0;123 }

 


联系
我们