AC自动机

AC自动机

AC自动机有一个很出色的功能:实现多模式匹配。

多模式匹配:模式串有多个,主串只有一个,要进行多次模式串匹配。如果用KMP就要一个一个模式串进行匹配,效率低。AC自动机就可以做到,只要经过一些预处理之后,扫描一遍主串,就可以找出所有模式串。

fail指针含义:若fail[i]=j,则word[j]word[i]的最长后缀。
fail指针的目的和意义:通过fail指针,把以s[i]为结尾的所有后缀的个数加起来,从而把匹配的模式串加起来。
如何构建fail指针:bfs层次遍历构建。
这个AC自动机感觉也可以 查后缀(想想fail指针的含义)

在这里插入图片描述

数据结构:

int n; //模式串个数
string s; //模式串
string text; //文本串
int trie[1000006][30],cnt[1000006],idx,fail[1000006]; //重要数据结构

先将输入的模式串构建成一棵字典树

void insert(string s)
{
	int p=0;
	for(int i=0;s[i];++i)
	{
		int c=s[i]-'a';
		if(!trie[p][c]) trie[p][c]=++idx;
		p=trie[p][c];
	}
	cnt[p]++;
}

再设置各个节点的fail指针:bfs(层次遍历)

void getfail()
{
	queue<int> q;
	for(int i=0;i<26;++i)
	{
		if(trie[0][i])
			q.push(trie[0][i]);
		fail[trie[0][i]]=0;
	}
	while(q.size())
	{
		int now=q.front();
		q.pop();
		for(int i=0;i<26;++i)
		{
			if(trie[now][i])
			{
				fail[trie[now][i]]=trie[fail[now]][i];
				q.push(trie[now][i]);
			}
			else
				trie[now][i]=trie[fail[now]][i];
		}
	}
}

遍历文本串,查询出有多少个匹配的模式串:

int query(string s)
{
	int now=0,ans=0;
	for(int i=0;s[i];++i)
	{
		now=trie[now][s[i]-'a'];
		for(int j=now;j&&cnt[j]!=-1;j=fail[j])
		{
			ans+=cnt[j];
			cnt[j]=-1;
		}
	}
	return ans;
}

分享B站学习链接:

1.[算法]轻松掌握ac自动机_哔哩哔哩_bilibili

刷题练手链接:

P3808 【模板】AC 自动机(简单版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

参考代码:

#include <bits/stdc++.h>
using namespace std;

int n;
string s;
string text;
int trie[1000006][30],cnt[1000006],idx,fail[1000006];
//vector<int> v[N]; //可以存编号为i的结点存放了字符串长度为多少的串 

void insert(string s)
{
	int p=0;
	for(int i=0;s[i];++i)
	{
		int c=s[i]-'a';
		if(!trie[p][c]) trie[p][c]=++idx;
		p=trie[p][c];
	}
	cnt[p]++;
}

void getfail()
{
	queue<int> q;
	for(int i=0;i<26;++i)
	{
		if(trie[0][i])
			q.push(trie[0][i]);
		fail[trie[0][i]]=0;
	}
	while(q.size())
	{
		int now=q.front();
		q.pop();
		for(int i=0;i<26;++i)
		{
			if(trie[now][i])
			{
				fail[trie[now][i]]=trie[fail[now]][i];
				q.push(trie[now][i]);
			}
			else
				trie[now][i]=trie[fail[now]][i]; //在构建fail指针时,trie在改变,它记录着 在上层 最近的 哪里 会有i这个元素 
		}
	}
}

int query(string s)
{
	int now=0,ans=0;
	for(int i=0;s[i];++i)
	{
//		cout<<i<<' '<<s[i]<<' '<<now<<' '<<trie[now][s[i]-'a']<<endl;
		now=trie[now][s[i]-'a'];
		for(int j=now;j&&cnt[j]!=-1;j=fail[j])
		{
//			cout<<j<<' '<<fail[j]<<endl; 
			ans+=cnt[j];
			cnt[j]=-1; //这个模板有个问题:只能做一次询问。
		}
	}
	return ans;
}

int main()
{
	cin >> n;
	while(n--)
	{
		cin >> s;
		insert(s);
	}
	cin >> text;
	getfail();
	cout << query(text) << endl;
	return 0;
}

模板注意点:
1.插入的字符可以是什么?一般是’a’-'z’共26种.但也有题目会说是 可见字符,可见字符 应该算95个,从32-126
2.如果有多个主串,要注意加一个bool flag[N]处理一下。

裸题:HDU-2222 Keywords Search

2017 ICPC 青岛网络赛 C-The Dominator of Strings
题意:多组样例,每次给出N个字符串,求出N个串的母串。
代码:一般参考以下模板!

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
int T,n,len;
string s,text;
int trie[100006][26],idx,fail[100006],cnt[100006];

void Init() {
    for(int i=0;i<=idx;i++){
        cnt[i]=0;
//        fail[i]=0;  
        for(int j=0;j<26;j++)
            trie[i][j]=0;
    }
    idx=0;
}

inline void insert(string s){
	int p=0;
	for(int i=0;s[i];++i){
		int c=s[i]-'a';
		if(!trie[p][c]) trie[p][c]=++idx;
		p=trie[p][c];
	}
	cnt[p]++;
}

/*
感觉以下做法:"有一个位置匹配了,就往后配" 这种做法 比较暴力
但有些题 竟然 跑得更快   很奇怪很奇怪很奇怪。。。 
*/ 
int query(string s){
	int ans=0;
	for(int i=0;s[i];++i){
		int c=s[i]-'a';
		int u=0;
		int j=0;
		while(trie[u][c]){
			if(cnt[trie[u][c]]){
				ans+=cnt[trie[u][c]];
				cnt[trie[u][c]]=0;
			}
			u=trie[u][c];
			j++;
			if(i+j>=s.size()) break; //注意加这一行!不然有些时候会寄! 
			c=s[i+j]-'a';
		}
	}
	return ans;
}

/*
正常的AC自动机 模板 
*/
//void getfail(){
//	queue<int> q;
//	for(int i=0;i<26;++i) {
//		if(trie[0][i]) q.push(trie[0][i]);
//		fail[trie[0][i]]=0;
//	}
//	while(q.size()){
//		int now=q.front();
//		q.pop();
//		for(int i=0;i<26;++i){
//			if(trie[now][i]){
//				fail[trie[now][i]]=trie[fail[now]][i];
//				q.push(trie[now][i]);
//			}else{
//				trie[now][i]=trie[fail[now]][i];
//			}
//		}
//	}
//}
//
//int query(string &s){
//	int now=0,ans=0;
//	for(int i=0;s[i];++i){
//		now=trie[now][s[i]-'a'];
//		for(int j=now;j&&cnt[j]!=-1;j=fail[j]){
//			ans+=cnt[j];
//			cnt[j]=-1;
//		}
//	}
//	return ans;
//}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		Init(); //学习! 
		len=0;
		for(int i=1;i<=n;++i) {
			cin>>s;
			insert(s);
			if(s.size()>len) text=s,len=s.size();
		}
//		getfail();
		if(query(text)==n) cout<<text<<'\n';
		else cout<<"No\n";
	}
}

例题:HDU - 2896 病毒侵袭
参考代码:
这道题 字符是可见字符,有多个主串

#include <bits/stdc++.h>
using namespace std;

int n,m;
string s,text;
vector<int> v;
int tot;

const int N=1e6+5;
int trie[N][100],cnt[N],idx,fail[N];
bool flag[N]; //标记 

void insert(string s,int id){
	int p=0;
	for(int i=0;s[i];++i){
		int c=s[i]-32;
		if(!trie[p][c]) trie[p][c]=++idx;
		p=trie[p][c];
	}
	cnt[p]=id;
}

void getfail(){
	queue<int> q;
	for(int i=0;i<95;++i){
		if(trie[0][i])
			q.push(trie[0][i]);
		fail[trie[0][i]]=0;
	}
	while(q.size()) {
		int now=q.front();
		q.pop();
		for(int i=0;i<95;++i){
			if(trie[now][i]){
				fail[trie[now][i]]=trie[fail[now]][i];
				q.push(trie[now][i]);
			}
			else trie[now][i]=trie[fail[now]][i];
		}
	}
}

void query(string s){
	int now=0;
	for(int i=0;s[i];++i){
		now=trie[now][s[i]-32];
		for(int j=now;j&&cnt[j]!=-1;j=fail[j]){
			if(cnt[j] && flag[j]) v.push_back(cnt[j]);
			flag[j]=0; //这个有个问题:只能查询一次 
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>s;
		insert(s,i);
	}
	getfail();
	cin>>m;
	for(int i=1;i<=m;++i){
		cin>>text;
		v.clear();
		for(int i=0;i<=idx;++i) if(cnt[i]) flag[i]=1; //为了实现多次扫描主串 
		query(text);
		if(v.size()){
			sort(v.begin(),v.end());
			tot++;
			cout<<"web "<<i<<":";
			for(auto x:v) cout<<' '<<x;
			cout<<'\n';
		}
	}
	cout<<"total: "<<tot<<'\n';
}

HDU - 3065 病毒侵袭持续中
这道题 主串有多个子串会跟模式串匹配要算多次
怎么办?答:去掉cnt[j]=-1 以及 条件的 cnt[i]!=-1
这样,主串出现多个模式串,就能算多次了 。
参考代码:

#include <bits/stdc++.h>
using namespace std;

int n;

#define pii pair<int,int>
#define fi first
#define se second
#define ms(a,x) memset(a,x,sizeof a)
//数据结构
const int N=5e4+10; //应该是模式串总长 
string s[1003],text;
int trie[N][100],cnt[N],idx,fail[N]
上一篇:神经网络的反向传播


下一篇:【图论】图论基础-存储