首页 > 代码库 > HDU 2222

HDU 2222

第一题AC自动机,高仿代码!

#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int maxn = 500010;char str[1000010];struct ACAutomaton{    int ch[maxn][26],fail[maxn],val[maxn],last[maxn],sz,root;    int newnode(){        memset(ch[sz],0,sizeof(ch[sz]));        val[sz] = 0;        return sz++;    }    void init(){        sz = 0;        root = newnode();    }    void insert(char *str){        int len = strlen(str);        int now = root;        for(int i = 0;i < len;i++){            int &tmp = ch[now][str[i]-a];            if(!tmp)    tmp = newnode();            now = tmp;        }        val[now]++;    }    void getfail(){        queue<int> q;        fail[root] = root;        for(int i = 0;i < 26;i++){            int u = ch[root][i];            if(u){                fail[u] = last[u] = 0;                q.push(u);            }        }        while(!q.empty()){            int now = q.front();q.pop();            for(int i = 0;i < 26;i++){                int u = ch[now][i];                if(!u)  ch[now][i] = ch[fail[now]][i];                else{                    fail[u] = ch[fail[now]][i];                    last[u] = val[fail[u]] ? fail[u]:last[fail[u]];                    q.push(u);                }            }        }    }    int query(char *str){        int len = strlen(str);        int now = root;        int ret = 0;        for(int i = 0;i < len;i++){            now = ch[now][str[i]-a];            int tmp = now;            while(tmp != root && val[tmp]){                ret += val[tmp];                val[tmp] = 0;                tmp = last[tmp];            }        }        return ret;    }}ac;int main(){    int kase,n;    scanf("%d",&kase);    while(kase--){        ac.init();        scanf("%d",&n);        for(int i = 0;i < n;i++){            scanf("%s",str);            ac.insert(str);        }        ac.getfail();        scanf("%s",str);        printf("%d\n",ac.query(str));    }    return 0;}