ac自动机模板
%yyb
通俗易懂的ac自动机教程 : https://www.cnblogs.com/cjyyb/p/7196308.html
板子题四道:
开一篇博客存一下板子(第一题ac代码)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 3;
struct Trie {
int fail,ch[27],cnt;
}ac[maxn];
int tot=0;
void Insert(char s[])
{
int len=strlen(s),now=0;
for(int i=0;i<len;i++) {
if(!ac[now].ch[s[i]-'a']) ac[now].ch[s[i]-'a']=++tot;
now=ac[now].ch[s[i]-'a'];
}
ac[now].cnt++;
}
void build()
{
ac[0].fail=0;
queue<int> q;
for(int i=0;i<26;i++) if(ac[0].ch[i])
{
ac[ac[0].ch[i]].fail=0; q.push(ac[0].ch[i]);
}
while(!q.empty())
{
int now=q.front(); q.pop();
for(int i=0;i<26;i++)
if(ac[now].ch[i])
{
ac[ac[now].ch[i]].fail=ac[ac[now].fail].ch[i];
q.push(ac[now].ch[i]);
}
else ac[now].ch[i]=ac[ac[now].fail].ch[i];
}
}
int query(char s[])
{
int len=strlen(s),ans=0,now=0,tmp;
for(int i=0;i<len;i++) {
now=ac[now].ch[s[i]-'a'];
tmp=now;
while(tmp&&ac[tmp].cnt)
{
ans+=ac[tmp].cnt;
ac[tmp].cnt=0;
tmp=ac[tmp].fail;
}
}
return ans;
}
int main()
{
int n;
char s[maxn];
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%s",s);
Insert(s);
}
build();
scanf("%s",s);
printf("%d",query(s));
return 0;
} 第四题代码(第一题改为多组数据需要每次初始化，初始化50*n的大小即可)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 3;
struct Trie {
int fail,ch[27],cnt;
}ac[maxn];
int tot=0;
void Insert(char s[])
{
int len=strlen(s),now=0;
for(int i=0;i<len;i++) {
if(!ac[now].ch[s[i]-'a']) ac[now].ch[s[i]-'a']=++tot;
now=ac[now].ch[s[i]-'a'];
}
ac[now].cnt++;
}
void build()
{
ac[0].fail=0;
queue<int> q;
for(int i=0;i<26;i++) if(ac[0].ch[i])
{
ac[ac[0].ch[i]].fail=0; q.push(ac[0].ch[i]);
}
while(!q.empty())
{
int now=q.front(); q.pop();
for(int i=0;i<26;i++)
if(ac[now].ch[i])
{
ac[ac[now].ch[i]].fail=ac[ac[now].fail].ch[i];
q.push(ac[now].ch[i]);
}
else ac[now].ch[i]=ac[ac[now].fail].ch[i];
}
}
int query(char s[])
{
int len=strlen(s),ans=0,now=0,tmp;
for(int i=0;i<len;i++) {
now=ac[now].ch[s[i]-'a'];
tmp=now;
while(tmp&&ac[tmp].cnt)
{
ans+=ac[tmp].cnt;
ac[tmp].cnt=0;
tmp=ac[tmp].fail;
}
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
char s[maxn];
scanf("%d",&n);
for(int i=0;i<=n*50;i++) {
ac[i].cnt=0;
for(int j=0;j<26;j++) ac[i].ch[j]=0;
}
for(int i=1;i<=n;i++) {
scanf("%s",s);
Insert(s);
}
build();
scanf("%s",s);
printf("%d\n",query(s));
}
return 0;
}
安克创新 Anker公司福利 778人发布
投递字节跳动等公司7个岗位