首页 > 代码库 > 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自动机)