首页 > 代码库 > hdu2222

hdu2222

数组开小了,还是小了很多,注意数组里的是节点总数!

#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#define maxn 500000+10using namespace std;int ch[maxn][26],fail[maxn],last[maxn],val[maxn],sz,root;int newnode(){    memset(ch[sz],0,sizeof(ch[sz]));    val[sz] = 0;    return sz++;}void init(){    sz =0;    root = newnode();}int 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]++;    return 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] = 0;            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;}int main(){    char str[1000010];    int n,m;    scanf("%d",&n);    while(n--)    {        init();        scanf("%d",&m);        for(int i =0;i< m;i++)        {            scanf("%s",str);            insert(str);        }        getfail();        scanf("%s",str);        printf("%d\n",query(str));    }    return 0;}