【HDU】病毒侵袭（AC自己主动机模板题）

AC自己主动机的模板题。因为输入的字符串中的字符不保证全为小写字母。所以范围应该在130之前，而前31位字符是不可能出如今字符串的（不懂得查下ACSII表即可了）。所以仅仅须要开的结点数组大小为130足够了。假设开256就会内存超限。

11908775

2014-10-19 10:45:38

Accepted

2896

250MS

29596K

G++

KinderRiven

输入仅仅有一组，所以不用操心超时的问题。

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 111111;

const int max_size = 130;

const int maxd = 222;

vector<int>G[1111];

struct Trie{

    int next[maxn][max_size];

    int fail[maxn];

    int  val[maxn];

    int sz;

    int root;

    int index(char e){

        return e - 31;

    }

    void init(){

        sz = 0;

        root = newnode();

    }

    int newnode(){

        val[sz] = 0;

        memset(next[sz],-1,sizeof(next[sz]));

        sz ++;

        return sz - 1;

    }

    void insert(char *str,int pos){

        int L = strlen(str);

        int u = root;

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

            int e = index(str[i]);

            if(next[u][e] == -1)

               next[u][e] = newnode();

           u = next[u][e];

        }

        val[u] = pos;

        //printf("%d %d\n",u,pos);

    }

    void build(){ //建立失配边

        fail[root] = root;

        queue<int>q;

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

            if(next[root][i] == -1)

               next[root][i] = root;

            else{

                fail[next[root][i]] = root;

                q.push(next[root][i]);

            }

        }

        while(!q.empty()){

            int now = q.front(); q.pop();

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

                if(next[now][i] == -1)

                   next[now][i] = next[fail[now]][i];

                else{

                   fail[next[now][i]] = next[fail[now]][i];

                   q.push(next[now][i]);

                }

            }

        }

    }

    void count(char *str,int pos){

        int L = strlen(str);

        int u = root;

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

            int e = index(str[i]);

            u = next[u][e];

            int temp = u;

            while(temp != root){

                if(val[temp] != 0)

                    G[pos].push_back(val[temp]);

                temp = fail[temp];

            }

        }

        return;

    }

};

Trie ac;

int main(){

    int n,m;

    ac.init();

    scanf("%d",&n);

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

        char str[maxd];

        scanf("%s",str);

        ac.insert(str,i);

    }

    //printf("%d\n",ac.sz);

    ac.build();

    scanf("%d",&m);

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

        char str[maxn];

        scanf("%s",str);

        ac.count(str,i);

    }

    int cnt = 0;

    for(int i = 1; i <= m; i++)if(G[i].size()){

        sort(G[i].begin(),G[i].end());

        cnt ++;

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

        for(int j = 0; j < G[i].size(); j++)

            printf(" %d",G[i][j]);

        printf("\n");

    }

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

}