AC自动机

前置知识

KMP
Trie

模板(code)

数组版

const int N=26;
const int Max=1e6+10;
const int Maxs=1e6+10;
struct Trie
{
    int nx[Max][N],fail[Max],end[Max];
    int root,tot;
    int newnode()
    {
        for(int i=0; i<N; i++)  nx[tot][i]=-1;
        end[tot++]=0;
        return tot-1;
    }
    void init(){    tot=0,root=newnode();   }
    void insert(char s[])
    {
        int len=strlen(s),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(nx[now][k]==-1)  nx[now][k]=newnode();
            now=nx[now][k];
        }
        end[now]++;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==-1) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==-1)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    int query(char s[])
    {
        int len=strlen(s),now=root,res=0,tmp;
        for(int i=0; i<len; i++)
        {
            now=nx[now][s[i]-'a'],tmp=now;
            while(tmp!=root&&end[tmp]!=-1)    res=res+end[tmp],end[tmp]=-1,tmp=fail[tmp];
        }
        return res;
    }
}ac;
char s[Maxs];

指针版

const int N=26;
const int Max=1e6+10;
char s[Max];
struct tree
{
	int end;
	tree *son[N],*fail;
};
struct Trie
{
	tree root;
    void init()
	{
		for(int i=0; i<N; i++)  root.son[i]=NULL;
        root.end=0;	
	}
    void insert(char s[])
    {
        int len=strlen(s),k;
        tree *now=&root;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(now->son[k]==NULL)
			{
				now->son[k]=new tree;
		        for(int i=0; i<N; i++)  now->son[k]->son[i]=NULL;
		        now->son[k]->end=0;
			}
            now=now->son[k];
        }
        now->end++;
    }
    void build()
    {
        queue<tree*> Q;
        root.fail=&root;
        for(int i=0; i<N; i++)
            if(root.son[i]==NULL) root.son[i]=&root;
            else    root.son[i]->fail=&root,Q.push(root.son[i]);
        tree* now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(now->son[i]==NULL)	now->son[i]=now->fail->son[i];
                else	now->son[i]->fail=now->fail->son[i],Q.push(now->son[i]);
        }
    }
    int query(char s[])
    {
        int len=strlen(s),res=0;
		tree *now=&root,*tmp;
        for(int i=0; i<len; i++)
        {
            now=now->son[s[i]-'a'],tmp=now;
            while(tmp!=&root&&tmp->end!=-1)    res=res+(tmp->end),tmp->end=-1,tmp=tmp->fail;
        }
        return res;
    }
}ac;

题目

P3808【模板】AC自动机（简单版）洛谷

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=26;
const int Max=1e6+10;
const int Maxs=1e6+10;
struct Trie
{
    int nx[Max][N],fail[Max],end[Max];
    int root,tot;
    int newnode()
    {
        for(int i=0; i<N; i++)  nx[tot][i]=-1;
        end[tot++]=0;
        return tot-1;
    }
    void init(){    tot=0,root=newnode();   }
    void insert(char s[])
    {
        int len=strlen(s),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(nx[now][k]==-1)  nx[now][k]=newnode();
            now=nx[now][k];
        }
        end[now]++;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==-1) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==-1)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    int query(char s[])
    {
        int len=strlen(s),now=root,res=0,tmp;
        for(int i=0; i<len; i++)
        {
            now=nx[now][s[i]-'a'],tmp=now;
            while(tmp!=root&&end[tmp]!=-1)    res=res+end[tmp],end[tmp]=-1,tmp=fail[tmp];
        }
        return res;
    }
}ac;
char s[Maxs];

void solve()
{
    int n;
    ac.init();
    scanf("%d",&n);
    for(int i=0; i<n; i++)  scanf("%s",s),ac.insert(s);
    ac.build();
    scanf("%s",s);
    cout<<ac.query(s)<<endl;
}

int main()
{
    solve();
    return 0;
}

P3796【模板】AC自动机（加强版）洛谷

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=26;
const int Max=500001;
const int Maxn=151;
const int Maxs=71;
const int Maxsss=1e6+10;
int n;
char s[Maxn][Maxs];
char sss[Maxsss];
struct Trie
{
	int nx[Max][N],fail[Max],end[Max],cnt[Maxn];
	int root,tot;
	int newnode()
	{
		for(int i=0; i<N; i++)	nx[tot][i]=-1;
		end[tot++]=-1;
		return tot-1;
	}
	void init(){	memset(cnt,0,sizeof(cnt)),tot=0,root=newnode();	}
	void insert(char s[],int pos)
	{
		int len=strlen(s),now=root,k;
		for(int i=0; i<len; i++)
		{
			k=(int)(s[i]-'a');
			if(nx[now][k]==-1)	nx[now][k]=newnode();
			now=nx[now][k];
		}
		end[now]=pos;
	}
	void build()
	{
		queue<int> Q;
		fail[root]=root;
		for(int i=0; i<N; i++)
			if(nx[root][i]==-1)	nx[root][i]=root;
			else	fail[nx[root][i]]=root,Q.push(nx[root][i]);
		int now;
		while(!Q.empty())
		{
			now=Q.front();Q.pop();
			for(int i=0; i<N; i++)
				if(nx[now][i]==-1)	nx[now][i]=nx[fail[now]][i];
				else	fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
		}
	}
	void query(char sss[])
	{
		int len=strlen(sss),now=root,res=0,tmp;
		for(int i=0; i<len; i++)
		{
			now=nx[now][sss[i]-'a'],tmp=now;
			while(tmp!=root)
			{
				if(end[tmp]!=-1)	cnt[end[tmp]]++,res=max(res,cnt[end[tmp]]);
				tmp=fail[tmp];
			}
		}
		printf("%d
",res);
		for(int i=0; i<n; i++)
			if(cnt[i]==res)
				cout<<s[i]<<endl;
	}
}ac;

int main()
{
	while(true)
	{
		scanf("%d",&n);
		if(n==0)	break;
		ac.init();
		for(int i=0; i<n; i++)	scanf("%s",s[i]),ac.insert(s[i],i);
		ac.build();
		scanf("%s",sss);
		ac.query(sss);
	}
	return 0;
}

P5357【模板】AC自动机（二次加强版）洛谷

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=26;
const int Maxn=200010;
const int Maxs=2000010;
int n;
char s[Maxs];
struct egde
{
	int y,nx;
}t[Maxs];int lt=0;
int head[Maxn];
bool v[Maxs];
struct Trie
{
    int nx[Maxs][N],fail[Maxs],end[Maxs],cnt[Maxn];
    int root,tot;
    int newnode()
    {
        for(int i=0; i<N; i++)  nx[tot][i]=-1;
        tot++;
        return tot-1;
    }
    void init()
	{
		memset(cnt,0,sizeof(cnt)),
		memset(head,-1,sizeof(head)),
		tot=0,root=newnode();
	}
    void insert(char s[],int pos)
    {
        int len=strlen(s),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(nx[now][k]==-1)  nx[now][k]=newnode();
            now=nx[now][k];
        }
        end[pos]=now;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==-1) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==-1)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    void query(char s[])
    {
        int len=strlen(s),now=root;
        for(int i=0; i<len; i++)
            now=nx[now][s[i]-'a'],cnt[now]++;
    }
	void add(int x, int y)
	{
		++lt;
		t[lt].y=y;
		t[lt].nx=head[x];
		head[x]=lt;
	}
    void calc()
    {
    	memset(v,false,sizeof(v));
    	for(int i=0; i<=tot; i++)	add(fail[i],i);
	}
	void dfs(int x)
	{
		v[x]=true;
		for(int i=head[x]; i!=-1; i=t[i].nx)
			if(!v[t[i].y])
			{
				dfs(t[i].y);
				cnt[x]+=cnt[t[i].y];
			}
	}
	void print()
	{
		for(int i=0; i<n; i++)
			printf("%d
",cnt[end[i]]);
	}
}ac;

int main()
{
    scanf("%d",&n);
    ac.init();
    for(int i=0; i<n; i++)
		scanf("%s",s),ac.insert(s,i);
    ac.build();
    scanf("%s",s);
	ac.query(s);
	ac.calc();
	ac.dfs(0);
	ac.print();
    return 0;
}

P3966 [TJOI2013]单词洛谷

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=27;
const int Maxn=200010;
const int Maxs=2000010;
int n;
struct egde
{
	int y,nx;
}t[Maxs];int lt=0;
int head[Maxn];
bool v[Maxs];
struct Trie
{
    int nx[Maxs][N],fail[Maxs],end[Maxs],cnt[Maxn];
    int root,tot;
	string s;
	string sss;
    int newnode()
    {
        for(int i=0; i<N; i++)  nx[tot][i]=-1;
        tot++;
        return tot-1;
    }
    void init()
	{
		memset(cnt,0,sizeof(cnt)),
		memset(head,-1,sizeof(head)),
		sss="";
		tot=0,root=newnode();
	}
    void insert(int pos)
    {
    	getline(cin,s);
		sss=sss+s+char('z'+1);
        int len=s.size(),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(nx[now][k]==-1)  nx[now][k]=newnode();
            now=nx[now][k];
        }
        end[pos]=now;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==-1) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==-1)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    void query()
    {
        int len=sss.size(),now=root;
        for(int i=0; i<len; i++)
            now=nx[now][sss[i]-'a'],cnt[now]++;
    }
	void add(int x, int y)
	{
		++lt;
		t[lt].y=y;
		t[lt].nx=head[x];
		head[x]=lt;
	}
    void calc()
    {
    	memset(v,false,sizeof(v));
    	for(int i=0; i<=tot; i++)	add(fail[i],i);
	}
	void dfs(int x)
	{
		v[x]=true;
		for(int i=head[x]; i!=-1; i=t[i].nx)
			if(!v[t[i].y])
			{
				dfs(t[i].y);
				cnt[x]+=cnt[t[i].y];
			}
	}
	void print()
	{
		for(int i=0; i<n; i++)
			printf("%d
",cnt[end[i]]);
	}
}ac;

int main()
{
    scanf("%d
",&n);
    ac.init();
    for(int i=0; i<n; i++)ac.insert(i);
    ac.build();
	ac.query();
	ac.calc();
	ac.dfs(0);
	ac.print();
    return 0;
}

P5231 [JSOI2012]玄武密码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=26;
const int Max=1e5+10;
int ans[Max];
char s[Max][101];
char sss[Max*100];
int m,n;
struct Trie
{
    int nx[Max*10][N],fail[Max*100];
    bool vis[Max*100];
    int root,tot;
    int newnode()
    {
        for(int i=0; i<N; i++)  nx[tot][i]=-1;
        tot++;
        return tot-1;
    }
    void init(){    tot=0,root=newnode();   }
    void insert(int pos)
    {
        int len=strlen(s[pos]),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[pos][i]-'A');
            if(nx[now][k]==-1)  nx[now][k]=newnode();
            now=nx[now][k];
        }
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==-1) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==-1)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    void query()
    {
        int len=strlen(sss),now=root,tmp;
        for(int i=0; i<len; i++)
        {
            now=nx[now][sss[i]-'A'],tmp=now;
            while(tmp!=root)
			{
				if(vis[tmp]) break;
				vis[tmp]=true;
				tmp=fail[tmp];
			}
        }
    }
    void getans(int pos)
    {
        int res=0,len=strlen(s[pos]),now=root;
        for(int i=0; i<len; i++)
        {
            now=nx[now][s[pos][i]-'A'];
            if(vis[now])	res=i+1;
        }
        cout<<res<<endl;
	}
}ac;

void solve()
{
    ac.init();
    scanf("%d%d",&m,&n);
    scanf("%s",sss);
    for(int i=0; i<n; i++)  scanf("%s",s[i]),ac.insert(i);
    ac.build();ac.query();
    for(int i=0; i<n; i++)	ac.getans(i);
}

int main()
{
    solve();
    return 0;
}

P4824 [USACO15FEB]Censoring (Silver) 审查(银)

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=26;
const int Maxn=1e5+10;
const int Maxs=1e6+10;
int n;
char s[Maxs],sss[Maxs];
struct Trie
{
    int nx[Maxn][N],fail[Maxn],end[Maxn];
    int last[Maxs],stack[Maxs];
    int root,tot;
    void init(){tot=0,root=tot++; }
    void insert(int pos)
    {
        int len=strlen(s),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(nx[now][k]==0)  nx[now][k]=tot++;
            now=nx[now][k];
        }
        end[now]=len;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==0) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==0)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    void query()
    {
        int len=strlen(sss),now=root,res=0,tmp,i=0,top=0;
		while(i<len)
        {
            now=nx[now][sss[i]-'a'],tmp=now;
            last[++top]=now;
            stack[top]=i;
            /*while(tmp!=root)
            {*/
                if(end[tmp])
                {
                	top=top-end[tmp];
                	if(!top)	now=0;
                	else   	now=last[top];
                //	break;
				}
               /* tmp=fail[tmp];
            }*/
            i++;
        }
        for(int i=1; i<=top; i++)
        	cout<<sss[stack[i]];
        cout<<endl;
    }
}ac;

int main()
{
	scanf("%s",sss);
    ac.init();
    scanf("%d
",&n);
    for(int i=0; i<n; i++)
    	scanf("%s",s),ac.insert(i);
    ac.build();
    ac.query();
    return 0;
}

P3121 [USACO15FEB]审查（黄金）Censoring (Gold)

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=26;
const int Maxn=1e6+10;
const int Maxs=1e7+10;
int n;
char s[Maxs],sss[Maxs];
struct Trie
{
    int nx[Maxn][N],fail[Maxn],end[Maxn];
    int last[Maxs],stack[Maxs];
    int root,tot;
    void init(){tot=0,root=tot++; }
    void insert(int pos)
    {
        int len=strlen(s),now=root,k;
        for(int i=0; i<len; i++)
        {
            k=(int)(s[i]-'a');
            if(nx[now][k]==0)  nx[now][k]=tot++;
            now=nx[now][k];
        }
        end[now]=len;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0; i<N; i++)
            if(nx[root][i]==0) nx[root][i]=root;
            else    fail[nx[root][i]]=root,Q.push(nx[root][i]);
        int now;
        while(!Q.empty())
        {
            now=Q.front();Q.pop();
            for(int i=0; i<N; i++)
                if(nx[now][i]==0)  nx[now][i]=nx[fail[now]][i];
                else    fail[nx[now][i]]=nx[fail[now]][i],Q.push(nx[now][i]);
        }
    }
    void query()
    {
        int len=strlen(sss),now=root,res=0,tmp,i=0,top=0;
		while(i<len)
        {
            now=nx[now][sss[i]-'a'],tmp=now;
            last[++top]=now;
            stack[top]=i;
            /*while(tmp!=root)
            {*/
                if(end[tmp])
                {
                	top=top-end[tmp];
                	if(!top)	now=0;
                	else   	now=last[top];
                //	break;
				}
               /* tmp=fail[tmp];
            }*/
            i++;
        }
        for(int i=1; i<=top; i++)
        	cout<<sss[stack[i]];
        cout<<endl;
    }
}ac;

int main()
{
	scanf("%s",sss);
    ac.init();
    scanf("%d
",&n);scanf("%s",s),ac.insert(1);
    ac.build();
    ac.query();
    return 0;
}