病毒侵袭持续中

HDOJ-3065

第一个需要注意的是树节点的个数也就是tree的第一维需要的空间是多少：模板串的个数*最长模板串的长度
一开始我的答案总时WA，原因是我的方法一开始不是这样做的，我是在查找文本串的时候，结束的时候再来统计每个模板串出现的次数，但是这样似乎不行
这道题还有一个坑就是输入是多组数据。。。

//AC自动机,复杂度为O(|t|+m),t表示文本串的长度，m表示模板串的个数

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<set>

using namespace std;

const int N=50004;//N的大小为模板串的长度乘以个数

int n;

string s[1002];

string t;

int cnt[1002];

struct ACM{

    int tree[N][128];//trie树上的结点，tree[i][j]表示i结点后面加一条j的边所对应的的结点

    int total;//总结点

    int num[N];//num[i]表示结点i上对应的模板串的编号,这里的空间大小要注意

    int fail[N];//失配指针，fail[i]指向所有模板串的前缀中匹配当前状态的最长后缀，指向的是最长后缀（和当前状态的后缀是匹配的，即相同，不过要最长）

    int val[N];//val[j]表示结点j所对应的模板串在文本串中出现的次数

    set<int> se;

    queue<int> q;

    void init(){

        total=0;

        fail[0]=num[0]=0;

        memset(tree,0,sizeof(tree));

        memset(val,0,sizeof(val));

        memset(fail,0,sizeof(fail));

        memset(num,0,sizeof(num));

        while(!q.empty())

            q.pop();

    }

    int idx(char c){//用来求字符c对应的编号（0-25）

        return c-0;

    }

    void insert(string s,int id){//类似于后缀树的插入一个模板串.id表示所有模板串中该模板串的编号

        int u=0;

        for(int i=0;i<s.length();i++){

            if(!tree[u][idx(s[i])])

                tree[u][idx(s[i])]=++total;

            u=tree[u][idx(s[i])];

        }

        num[u]=id;

    }

    void build(){//建AC自动机以及fail数组

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

            if(tree[0][i]){

                q.push(tree[0][i]);

                fail[tree[0][i]]=0;

            }

        }

        while(!q.empty()){

            int u=q.front();

            //cout<<u<<endl;

            q.pop();

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

                if(tree[u][i]){//如果结点u连的边为i对应的结点存在，则将这个存在的结点的fail指针指向父节点失配指针指向的结点的连的边为i所对应的的结点

                    fail[tree[u][i]]=tree[fail[u]][i];

                    q.push(tree[u][i]);

                }else{//类似于状态压缩，不至于每次fail指针跳转很多次，只需每次跳转一次，相当于构建了图

                    tree[u][i]=tree[fail[u]][i];

                }

            }

        }

    }

    void query(string t){//s为要查找的文本串

        int u=0;

        int res=0;//记录答案，所有的模板串共出现了多少次

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

            u=tree[u][idx(t[i])];

             for(int j=u;j>0&&num[j];){

                cnt[num[j]]++;

                j=fail[j];

            }

        }

    }

};

ACM ac;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    while(cin>>n){

        memset(cnt,0,sizeof(cnt));

        ac.init();

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

            cin>>s[i];

            ac.insert(s[i],i);

        }

        ac.build();

        cin>>t;

        ac.query(t);

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

            if(cnt[i]>0){

                cout<<s[i]<<": "<<cnt[i]<<endl;

            }

        }

    }

    //system("pause");

    return 0;

}

巴特西

HDOJ-3065(AC自动机+每个模板串的出现次数）

病毒侵袭持续中

HDOJ-3065

最新文章

热门文章