AC自动机 HDU 2222

t

n个字串

1个母串

求出现几个字串

字串可能重复

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<queue>

using namespace std;

class node

{

public:

    int mark;

    node *fail;

    node * next[];

    node()

    {

        mark=;

        fail=;

        memset(next,,sizeof(next));

    }

};

bool flag[];

char s1[];

node *root;

queue<node *>q1;

void Insert(char *s,int id)

{

    node *p=root;

    while(*s)

    {

        int ind=*s-'a';

        if(p->next[ind]==NULL)

            p->next[ind]=new node;

        p=p->next[ind];

        s++;

    }

    p->mark++;

}

void Build()

{

    q1.push(root);

    root->fail=;

    while(!q1.empty())

    {

        node *p=NULL;

        node *now=q1.front();

        q1.pop();

        for(int i=;i<;i++)

        {

            if(now->next[i])

            {

                if(now==root)

                    now->next[i]->fail=root;

                else

                {

                    p=now->fail;

                    while(p)

                    {

                        if(p->next[i])

                        {

                            now->next[i]->fail=p->next[i];

                            break;

                        }

                        p=p->fail;

                    }

                    if(p==NULL)

                        now->next[i]->fail=root;

                }

                q1.push(now->next[i]);

            }

        }

    }

}

void dfs(node *p)

{

    for(int i=;i<;i++)

        if(p->next[i])

            dfs(p->next[i]);

    delete p;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

        root=new node;

        for(int i=;i<=n;i++)

        {

            char s[];

            scanf("%s",s);

            Insert(s,i);

        }

        Build();

        scanf("%s",s1);

        int ans=;

        int len=strlen(s1);

        node *p=root;

        for(int i=;i<len;i++)

        {

            int ind=s1[i]-'a';

            while(p->next[ind]==NULL&&p!=root)

                p=p->fail;

            p=p->next[ind];

            if(!p)

                p=root;

            node *now=p;

            while(now!=root&&now->mark!=-)

            {

                ans+=now->mark;

                now->mark=-;

                now=now->fail;

            }

        }

        printf("%d\n",ans);

        dfs(root);

    }

    return ;

}