首页 > 代码库 > hdu 3065病毒侵袭持续中(ac自动机)
hdu 3065病毒侵袭持续中(ac自动机)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=3065
中文题题意不解释了。
依旧稍微改一下ac自动机模版就能过了。还有一个坑点!是多组数据!!!
#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;const int M = 5e4 + 10 , MM = 2e6 + 10 , N = 1e3 + 10;char str[N][60] , sl[MM];int Next[M][27] , fail[M] , End[M] , c[M / 10] , L , root , cnt , ans;int newnode() { for(int i = 0 ; i <= 26 ; i++) { Next[L][i] = -1; } End[L++] = 0; return L - 1;}void init() { L = 0 , ans = 0; root = newnode(); memset(c , 0 , sizeof(c));}void build(char s[]) { int len = strlen(s); int now = root; for(int i = 0 ; i < len ; i++) { int id = s[i] - ‘A‘; if(Next[now][id] == -1) { Next[now][id] = newnode(); } now = Next[now][id]; } End[now] = ++ans;}void get_fail() { queue<int>q; fail[root] = root; for(int i = 0 ; i <= 26 ; i++) { if(Next[root][i] == -1) { Next[root][i] = root; } else { fail[Next[root][i]] = root; q.push(Next[root][i]); } } while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 0 ; i <= 26 ; i++) { if(Next[now][i] == -1) { Next[now][i] = Next[fail[now]][i]; } else { fail[Next[now][i]] = Next[fail[now]][i]; q.push(Next[now][i]); } } }}void match(char s[]) { int len = strlen(s); int now = root; for(int i = 0 ; i < len ; i++) { int id; if(s[i] <= ‘Z‘ && s[i] >= ‘A‘) { id = s[i] - ‘A‘; } else { id = 26; } now = Next[now][id]; int tmp = now; while(tmp != root) { if(End[tmp] > 0) { c[End[tmp]]++; } tmp = fail[tmp]; } }}int main(){ int n; while(scanf("%d" , &n) != EOF) { init(); for(int i = 0 ; i < n ; i++) { scanf("%s" , str[i + 1]); build(str[i + 1]); } getchar(); get_fail(); gets(sl); match(sl); for(int i = 0 ; i < n ; i++) { if(c[i + 1] != 0) { printf("%s: %d\n" , str[i + 1] , c[i + 1]); } } } return 0;}
hdu 3065病毒侵袭持续中(ac自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。