首页 > 代码库 > HDU 3065 病毒侵袭持续中(AC自动机)
HDU 3065 病毒侵袭持续中(AC自动机)
这题数据太水,一开始没有加上Get的方法也能AC。。话说AC自动机中一定要注意加上Get的方法!(不然,同一个后缀的其他单词就没被算上了。)
代码如下:
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <queue> 5 #include <string> 6 #include <map> 7 #include <iostream> 8 using namespace std; 9 const int MAX_N = 2000000 + 50; 10 const int MAX_Tot = 1000*50 + 50; 11 12 int ans[1000+5]; 13 map<int,string> M; 14 15 struct Aho 16 { 17 struct state 18 { 19 int nxt[26]; 20 int fail,cnt; 21 }stateTable[MAX_Tot]; 22 23 int size; 24 25 queue<int> que; 26 27 void init() 28 { 29 while(que.size()) que.pop(); 30 for(int i=0;i<MAX_Tot;i++) 31 { 32 memset(stateTable[i].nxt,0,sizeof(stateTable[i].nxt)); 33 stateTable[i].fail = stateTable[i].cnt = 0; 34 } 35 size = 1; 36 } 37 38 void insert(char *s,int which) 39 { 40 int n = strlen(s); 41 int now = 0; 42 for(int i=0;i<n;i++) 43 { 44 char c = s[i]; 45 if(!stateTable[now].nxt[c-‘A‘]) 46 stateTable[now].nxt[c-‘A‘] = size++; 47 now = stateTable[now].nxt[c-‘A‘]; 48 } 49 stateTable[now].cnt = which; 50 } 51 52 void build() 53 { 54 stateTable[0].fail = -1; 55 que.push(0); 56 57 while(que.size()) 58 { 59 int u = que.front();que.pop(); 60 for(int i=0;i<26;i++) 61 { 62 if(stateTable[u].nxt[i]) 63 { 64 if(u == 0) stateTable[stateTable[u].nxt[i]].fail = 0; 65 else 66 { 67 int v = stateTable[u].fail; 68 while(v != -1) 69 { 70 if(stateTable[v].nxt[i]) 71 { 72 stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i]; 73 break; 74 } 75 v = stateTable[v].fail; 76 } 77 if(v == -1) stateTable[stateTable[u].nxt[i]].fail = 0; 78 } 79 que.push(stateTable[u].nxt[i]); 80 } 81 } 82 } 83 } 84 85 void Get(int u) 86 { 87 while(u) 88 { 89 ans[stateTable[u].cnt] ++; 90 u = stateTable[u].fail; 91 } 92 } 93 94 void match(char *s) 95 { 96 int n = strlen(s); 97 int now = 0; 98 for(int i=0;i<n;i++) 99 { 100 char c = s[i]; 101 if(c<‘A‘ || c>‘Z‘) {now = 0;continue;} 102 if(stateTable[now].nxt[c-‘A‘]) now = stateTable[now].nxt[c-‘A‘]; 103 else 104 { 105 int p = stateTable[now].fail; 106 while(p != -1 && stateTable[p].nxt[c-‘A‘] == 0) p = stateTable[p].fail; 107 if(p == -1) now = 0; 108 else now = stateTable[p].nxt[c-‘A‘]; 109 } 110 if(stateTable[now].cnt) 111 { 112 Get(now); 113 //ans[stateTable[now].cnt] ++; 114 /* 115 一定要用Get这样的方法, 116 不然,同一个后缀的无法被算上了 117 */ 118 } 119 } 120 } 121 }aho; 122 123 int n; 124 char s[MAX_N]; 125 126 int main() 127 { 128 while(scanf("%d",&n)==1) 129 { 130 memset(ans,0,sizeof(ans)); 131 M.clear(); 132 aho.init(); 133 for(int i=1;i<=n;i++) 134 { 135 scanf("%s",s); 136 M[i] = s; 137 aho.insert(s,i); 138 } 139 aho.build(); 140 scanf("%s",s); 141 aho.match(s); 142 for(int i=1;i<=n;i++) 143 { 144 if(ans[i]) 145 { 146 cout << M[i] << ": " << ans[i] << endl; 147 } 148 } 149 } 150 }
HDU 3065 病毒侵袭持续中(AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。