欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu2896(AC自动机)

程序员文章站 2022-06-06 20:56:47
...

这个题有一个非常坑的点 就是网址不一定是小写字母!!

还有就是这个题卡空间卡到令人窒息 子节点数组开到130即可 节点最大个数210*500即可

但是要注意不是小写字母的话下文代码处原本的s[j]-'a'要变为s[j]-'\0'

(不如叫RE-ME-WA自动机好了)

hdu2896(AC自动机)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
const int maxn = 210*500;
char str[10000+100];
vector<int>res;
struct node{
    int fail;
    int cnt;
    int next[130];

}tree[maxn];
bool vis[maxn];
int k =0,ans = 0;
queue<int>q;
map<int,int>mp;

void build_tree(int id, char *s, int bi){
    int len = strlen(s);
    for(int i =0;i<len;++i){
        int j =s[i]-'\0';
        if(tree[id].next[j]==0){
            tree[id].next[j]=++k;
        }
        id = tree[id].next[j];

    }
    mp[id] = bi;
    tree[id].cnt++;
}

void build_fail(int id){

    while(!q.empty())q.pop();
    for(int i =0;i<130;++i){
        int j =tree[id].next[i];
        if(j){
            q.push(j);
            tree[j].fail = id;
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0;i<130;++i){
            int j = tree[now].next[i];
            if(j==0){
                tree[now].next[i] = tree[tree[now].fail].next[i];
                continue;
            }
            tree[j].fail = tree[tree[now].fail].next[i];
            q.push(j);

        }
    }
}

void solve(int id, char *s){
    int len = strlen(s),j=0;
    for(int i =0;i<len;++i){
        int j = tree[id].next[s[i]-'\0'];
        while(j&&!vis[j]){
            ans+=tree[j].cnt;
            if(tree[j].cnt){
                res.push_back(mp[j]);
            }
            vis[j]=true;
            j = tree[j].fail;
        }

        id = tree[id].next[s[i]];

    }

}

int main(){
    int n;
    scanf("%d",&n);
    for(int i =1;i<=n;++i){
        scanf("%s",str);
        build_tree(0,str,i);
    }

build_fail(0);
    int m;

    scanf("%d",&m);
    int total = 0;
    int c= 1;
    while(m--){
           // cout<<c<<endl;
        //
        memset(vis,false,sizeof(vis));
        res.clear();
        ans = 0;
        scanf("%s",str);
        solve(0,str);
        if(ans){
            sort(res.begin(),res.end());
            cout<<"web "<<c<<":";
            for(int i =0;i<res.size();++i){
                cout<<" "<<res[i];
            }
            cout<<endl;
            total++;
        }
        c++;

    }
    cout<<"total"<<":"<<" "<<total<<endl;


}