首页 > 代码库 > HDU 2222 最简单的AC自动机套模板应用

HDU 2222 最简单的AC自动机套模板应用

2024-07-15 22:28:22   217人阅读

HDU 2222 题意：给出N(N<=10,000)个单词，每个单词长度不超过50。再给出一个字符串S，字符串长度不超过1,000,000。问有多少个单词出现在了字符串S中。（单词可能重复，单词在S中允许重叠）

我们在val[]数组中记录重复的个数

因为在主串对他进行匹配时，匹配到一次后这个重复次数就不应该继续添加了，所以在query中val[]要对它进行清零操作

#include <cstdio>#include <cstring>#include <queue>using namespace std;#define N 500005char str[1000005];struct AC{    int ch[N][26],fail[N],val[N],last[N],tmp,root;    int newnode(){        val[tmp]=0;        memset(ch[tmp],0,sizeof(ch[tmp]));        return tmp++;    }    void init(){        tmp=0;        root=newnode();    }    void add(char *s){        int len=strlen(s);        int now=root;        for(int i=0;i<len;i++){            int &k=ch[now][s[i]-‘a‘];            if(!k) k=newnode();            now=k;        }        val[now]++;    }    void get_fail(){        fail[root]=root;        queue<int> q;        for(int i=0;i<26;i++){            int v=ch[root][i];            if(v)                fail[v]=last[v]=0,q.push(v);        }        while(!q.empty()){            int now=q.front();            q.pop();            for(int i=0;i<26;i++){                int v=ch[now][i];                if(!v) ch[now][i]=ch[fail[now]][i];                else{                    fail[v]=ch[fail[now]][i];                    last[v]=val[fail[v]]?fail[v]:last[fail[v]];                    q.push(v);                }            }        }    }    int query(char *str){        int len=strlen(str);        int now=root,ret=0;        for(int i=0;i<len;i++){            now=ch[now][str[i]-‘a‘];            int k=now;            while(k!=root&&val[k]){//这是要循环到找到fail值为root的时候或者找到匹配的字符串的时候，否则一直向前找fail值，                ret+=val[k];                val[k]=0;                k=last[k];            }        }        return ret;    }}ac;int main(){    int T,n;    scanf("%d",&T);    while(T--){        ac.init();        scanf("%d",&n);        for(int i=0;i<n;i++){            scanf("%s",str);            ac.add(str);        }        ac.get_fail();        scanf("%s",str);        int ans=ac.query(str);        printf("%d\n",ans);    }    return 0;}
View Code

 


联系
我们