AC自动机例题

P3808 [模板]AC自动机(简单版)
[题目描述]
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

#include
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x;
}const int MAXN=1e6+5;
const int MAXV=26;namespace ACzdj{struct Trie{int v[MAXV];int fail,end;}AC[MAXN];int Ncnt;inline void build(string s){int cur=0,l=s.length();for(int i=0;i q;for(int i=0;i<26;i++)if(AC[0].v[i]){AC[AC[0].v[i]].fail=0;q.push(AC[0].v[i]);}while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<26;i++){if(AC[u].v[i]){AC[AC[u].v[i]].fail=AC[AC[u].fail].v[i];q.push(AC[u].v[i]);}elseAC[u].v[i]=AC[AC[u].fail].v[i];}}}inline int query(string s){int res=0;int l=s.length(),cur=0;for(int i=0;i>s;build(s);}AC[0].fail=0;Get_fail();cin>>s;printf("%d\n",query(s));
}

P3796 [模板]AC自动机(加强版)
[题目描述]
有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。

// luogu-judger-enable-o2
#include
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x;
}const int MAXN=150000;
const int MAXM=155;
const int MAXV=26;struct Node{int num,id;friend bool operator < (Node a,Node b){if(a.num==b.num) return a.idb.num;}
}ans[MAXM];namespace ACzdj{struct Trie{int v[MAXV];int fail,end;}AC[MAXN];int Ncnt;inline void clear(int x){for (register int i = 0; i < 26; ++i)AC[x].v[i] = 0;AC[x].fail=0,AC[x].end=0;}inline void build(const string& s,int id){int cur=0,l=s.length();for(int i=0;i q;for(int i=0;i<26;i++)if(AC[0].v[i]){AC[AC[0].v[i]].fail=0;q.push(AC[0].v[i]);}while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<26;i++){if(AC[u].v[i]){AC[AC[u].v[i]].fail=AC[AC[u].fail].v[i];q.push(AC[u].v[i]);}elseAC[u].v[i]=AC[AC[u].fail].v[i];}}}inline void query(const string& s){int l=s.length(),cur=0;for(int i=0;i>s[i];ans[i].num=0,ans[i].id=i;build(s[i],i);}AC[0].fail=0;Get_fail();cin>>s[0];query(s[0]);sort(ans+1,ans+n+1);printf("%d\n",ans[1].num);cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！