HDU2896【AC自动机-模板】

思路：

因为不同病毒特征码不会相同。

AC自动机，然后对于每一个输出即可。
注意：以上字符串中字符都是ASCII码可见字符（不包括回车）;G++ MLE。
//#include <bits/stdc++.h>

#include<iostream>

#include<queue>

#include<cstdio>

#include<string.h>

#include<algorithm>

using namespace std;

const int N=1e5+10;    //500个串，长度为200

struct Trie{

    int num;

    Trie *next[128],*fail;

};

Trie q[N],*root;

int tol;

Trie* Creat()

{

    Trie *p;

    p=&q[tol++];

    p->fail=NULL;

    p->num=0;

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

        p->next[i]=NULL;

    return p;

}

void Insert(char *str,int num)

{

    int len=strlen(str),index;

    Trie *p=root;

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

    {

        index=str[i];

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

            p->next[index]=Creat();

        p=p->next[index];

    }

    p->num=num;

}

void Build_Ac()

{

    queue<Trie*>que;

    que.push(root);

    while(!que.empty())

    {

        Trie *p=que.front();que.pop();

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

        {

            if(p->next[i]!=NULL)

            {

                if(p==root) p->next[i]->fail=root;

                else{

                    Trie *temp=p->fail;

                    while(temp!=NULL)

                    {

                        if(temp->next[i]!=NULL) {

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

                            break;

                        }

                        temp=temp->fail;

                    }

                    if(temp==NULL)

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

                }

                que.push(p->next[i]);

            }

        }

    }

}

int ans[510],nn;

char word[10010];

void Query()

{

    Trie *p=root;

    int index,len=strlen(word);

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

    {

        index=word[i];

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

            p=p->fail;

        p=p->next[index];

        if(p==NULL)

            p=root;

        Trie *temp=p;

        while(temp!=root)

        {

            if(temp->num)

                ans[nn++]=temp->num;

            temp=temp->fail;

        }

    }

}

char s[220];

int main()

{

    tol=0;

    root=Creat();

    int n,m;

    scanf("%d",&n);

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

    {

        scanf("%s",s);

        Insert(s,i);

    }

    Build_Ac();

    scanf("%d",&m);

    int sum=0;

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

    {

        scanf("%s",word);

        nn=0;

        Query();

        if(nn)

        {

            sum++;

            sort(ans,ans+nn);

            printf("web %d:",i);

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

                printf(" %d",ans[i]);

            puts("");

        }

    }

    printf("total: %d\n",sum);

    return 0;

}
巴特西

HDU2896【AC自动机-模板】

最新文章

热门文章
