POJ 2896 AC自动机 or 暴力

DESCRIPTION ：大意是说。给你n个代表病毒的字符串。m个表示网站的字符串。让你计算有多少个网站被病毒感染了。被那些病毒感染了。

刚开始就想暴力。然而，忽略了条件：每个网站最多有三个病毒。于是。TLE了。于是换AC 自动机。于是MLE了。于是把最大的结构体指针数组换成队列。用时间来换空间。23333

应该注意结构体的初始化是必须的。

附代码：
AC 自动机：

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<queue>

#include<algorithm>

#include<map>

using namespace std;

#define T_SIZE 10000

struct trie{

    trie* nexts[128];

    trie* fail;

    int num1, num2;

    int mem;

    trie(){

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

            nexts[i]=NULL;

        }

        fail=NULL;

        num1= num2 = 0;

    }

};

char T[T_SIZE+2];

queue<struct trie*>que;

int ans[50];

map<int, int>mm;

void insert(trie* root,char* s, int m){

    trie* p=root;

    for(int i=0;s[i]!='\0';i++){

        if(p->nexts[s[i]-0]==NULL)

            p->nexts[s[i]-0]=new trie;

        p=p->nexts[s[i]-0];

    }

    p->num1++;

    p->mem = m;

}

void build_ac_automation(trie* root){

    que.push(root);

    while(!que.empty()){

        trie* fronts=que.front();

        que.pop();

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

            if(fronts->nexts[i]!=NULL){

                trie* p=fronts->fail;

                while(p!=NULL){

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

                        fronts->nexts[i]->fail=p->nexts[i];

                        break;

                    }

                    p=p->fail;

                }

                if(p==NULL){

                    fronts->nexts[i]->fail=root;

                }

                que.push(fronts->nexts[i]);

            }

        }

    }

}

int ac_find(trie* root,char* T){

    trie* p=root;

    int sum=0;

    memset(ans,0,sizeof(ans));

    for(int i=0,len=strlen(T);i<len;i++){

        while(p->nexts[T[i]-0]==NULL && p!=root)

            p=p->fail;

        if(p->nexts[T[i]-0]!=NULL){

            p=p->nexts[T[i]-0];

        }

        trie* temp=p;

        temp->num2 = temp->num1;

        while(temp!=root && temp->num2!=-1){

            temp->num2 = temp->num1;

            if (!mm[temp->mem])

            {ans[sum]=temp->mem+1;

            sum+=temp->num2;}

            temp->num2=-1;

            temp=temp->fail;

        }

    }

    return sum;

}

int main(){

    int n;

    while(scanf("%d",&n)!= EOF){

            mm.clear();

            int summ=0;

        trie* root=new trie;

        getchar();

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

            memset(T,0,sizeof(T));

            gets(T);

            insert(root,T, i);

        }

        build_ac_automation(root);

        int t;

        scanf("%d",&t);

        getchar();

        for(int i=0;i<t;i++){

            memset(T,0,sizeof(T));

            gets(T);

            int num=ac_find(root,T);

            if(num!=0){

                summ++;

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

                sort(ans, ans+num);

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

                for(int j=1;j<num;j++){

                    if (ans[j] == ans[j-1])

                        continue;

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

                }

                printf("\n");

            }

        }

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

    }

    return 0;

}

巴特西

POJ 2896 AC自动机 or 暴力

最新文章

热门文章