AC自动机模版题

似乎要注意如果某个节点x的fail是可接受的,那么x也是可接受的

还有对于root的child的fail要特判强制扔到root上

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    bool accept;
    int val1;
    int val2;
    node * ch[26];
    node * fail;
};
char a[105];
node * new_node()
{
    static node a[100005];
    static int top=0;
    memset(a[top].ch,0,sizeof(a[top].ch));
    a[top].fail=0;
    a[top].accept=false;
    return &a[top++];
}
const int modo=10007;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    node * root=new_node();
    for (i=0;i<n;i++)
    {
        scanf("%s",a);
        int j;
        node * now=root;
        for (j=0;a[j]!='\0';j++)
        {
            if (now->ch[a[j]-'A']==0)
            {
                now->ch[a[j]-'A']=new_node();
            }
            now=now->ch[a[j]-'A'];
        }
        now->accept=true;
    }
    static node * que[6005];
    int front=0,rail=1;
    que[0]=root;
    for (;front<rail;front++)
    {
        int i;
        for (i=0;i<26;i++)
        {
            if (que[front]->ch[i]==0) continue;
            que[rail++]=que[front]->ch[i];
        }
    }
    root->fail=root;
    for (i=0;i<26;i++)
    {
        if (root->ch[i]==0) root->ch[i]=root;
    }
    for (i=0;i<rail;i++)
    {
        int j;
        node * t=que[i];
        for (j=0;j<26;j++)
        {
            if (t->ch[j]==0)
            {
                t->ch[j]=t->fail->ch[j];
            }
            else
            {
                t->ch[j]->fail=t->fail->ch[j];
                if (t==root) t->ch[j]->fail=root;
                if (t->ch[j]->fail->accept) t->ch[j]->accept=true;
            }
        }
    }
    root->val2=1;
    int p=1;
    for (i=0;i<m;i++)
    {
        p*=26;
        p%=modo;
        int j;
        for (j=0;j<rail;j++)
        {
            que[j]->val1=que[j]->val2%modo;
            que[j]->val2=0;
        }
        for (j=0;j<rail;j++)
        {
            if (que[j]->accept) continue;
            int k;
            for (k=0;k<26;k++)
            {
                que[j]->ch[k]->val2+=que[j]->val1;
            }
        }
    }
    for (i=0;i<rail;i++)
    {
        if (que[i]->accept) continue;
        p-=que[i]->val2;
        p%=modo;
    }
    p+=modo;
    printf("%d\n",p%modo);
    return 0;
}