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];
vector<pii> v;
unordered_map<int,int> mp; 

void insert(string s,int k){
	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]=k;
}

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];
		}
	}
}

void query(string s){
	int now=0;
	for(int i=0;s[i];++i){
		if(s[i]>'Z' || s[i]<'A') {
			now=0;
			continue;
		}
		now=trie[now][s[i]-'A'];
		for(int j=now;j;j=fail[j]){
			if(cnt[j]) mp[cnt[j]]++;
		}
	}
}

bool cmp(pii x,pii y){
	return x.fi<y.fi;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(cin>>n){
		ms(trie,0);
		ms(cnt,0);
		ms(fail,0);
		idx=0;
		v.clear();
		mp.clear();
		for(int i=1;i<=n;++i){
			cin>>s[i];
			insert(s[i],i);
		}
		getfail();
		cin>>text;
		query(text);
		for(auto x:mp) v.push_back(x); 
		sort(v.begin(),v.end(),cmp);
		for(auto x:v){
			cout<<s[x.fi]<<": "<<x.se<<'\n';
		}
	}
}
由若干模式串构建串

HDU - 2825 Wireless Password
题意：给你M个模式串，问有多少种方案 构造长度为N的 至少包含K个模式串的 串。
注意：
1.字符串会包含，如有模式串she he，串she包含由模式串she和he
有一点 串包含 的意思在里面，所以可以想到用AC自动机把模式串全部扔进去。
2.然后用状压dp进行转移

参考

代码：

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

const int N=110;
const int MOD=20090717;
int trie[N][26],fail[N],cnt[N],idx;
int n,m,k;
string s;
int dp[30][110][1<<10]; //dp[i][j][k]:走到第i步 到达j结点 状态为k 的方案数 
int num[1<<10]; //num[i]:状态为i的1的数目 

void insert(string s,int id){
	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]=1<<id;
}

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();
		cnt[now]|=cnt[fail[now]]; //因为提到 字符串 后缀包含 
		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];
		}
	}
}

void getsum(){
	for(int i=0;i<(1<<10);++i){
		num[i]=0;
		for(int j=0;j<10;++j)
			if(i&(1<<j)) num[i]++;
	}
} 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	getsum(); //预处理 
	while(cin>>n>>m>>k && (n||m||k)){
		memset(trie,0,sizeof trie);
		memset(fail,0,sizeof fail);
		memset(cnt,0,sizeof cnt);
		idx=0; 
		memset(dp,0,sizeof dp);
		for(int i=1;i<=m;++i) {
			cin>>s;
			insert(s,i-1);
		}
		getfail();
		dp[0][0][0]=1; 
		for(int i=0;i<n;++i){ //遍历字符 
			for(int j=0;j<=idx;++j){ //遍历结点编号 
				for(int kk=0;kk<(1<<m);++kk){ //遍历状态 
					if(dp[i][j][kk]){
						for(int id=0;id<26;++id){ //遍历j号点下面的各个分支点 
							int u=trie[j][id];
							int state=kk|cnt[u];
							dp[i+1][u][state]+=dp[i][j][kk];
							dp[i+1][u][state]%=MOD;
						}
					} 
				}
			}
		} 
		int ans=0;
		for(int i=0;i<(1<<m);++i){
//			cout<<num[i]<<endl;
			if(num[i]>=k){
				for(int j=0;j<=idx;++j){
					ans=(ans+dp[n][j][i])%MOD;
				}
			}
		}
		cout<<ans<<endl;
	}
	
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/586806.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

深度学习中权重初始化的重要性

深度学习中权重初始化的重要性

深度学习模型中的权重初始化经常被人忽略&#xff0c;而事实上这是非常重要的一个步骤&#xff0c;模型的初始化权重的好坏关系到模型的训练成功与否&#xff0c;以及训练速度是否快速&#xff0c;效果是否更好等等&#xff0c;这次我们专门来看看深度学习中的权重初始化问题。…
阅读更多...
RuoYi-Vue-Plus （SPEL 表达式）

RuoYi-Vue-Plus （SPEL 表达式）

RuoYi-Vue-Plus 中SPEL使用 DataScopeType 枚举类中&#xff1a; /*** 部门数据权限*/DEPT("3", " #{#deptName} #{#user.deptId} ", " 1 0 "), PlusDataPermissionHandler 拦截器中定义了解析器&#xff1a; buildDataFilter 方法中根据注解的…
阅读更多...
基于电磁激励原理利用视触觉传感器估计抓取力矩的方法

基于电磁激励原理利用视触觉传感器估计抓取力矩的方法

由于触觉感知能使机器人通过其触觉传递获取丰富的接触信息&#xff0c;触觉感知已经成为机器人机械臂的一种流行的感知方式。而在触觉传感器可获取的各种信息中&#xff0c;通过外界接触从抓取物体传递到机器人手指的力矩等信息&#xff0c;在完成各种指令的实现尤为重要。如图…
阅读更多...
数据结构––队列

数据结构––队列

1.队列的定义 2.队列的分类 2.1循环队 2.2链式队 3.队列的实现 3.1循环队 3.1.1声明 typedef int QDataType; #define MAXSIZE 50 //定义元素的最大个数 /*循环队列的顺序存储结构*/ typedef struct {QDataType *data;int front; //头指针int rear; //尾指针 }Queue;…
阅读更多...
【最大公约数 排序】2344. 使数组可以被整除的最少删除次数

【最大公约数 排序】2344. 使数组可以被整除的最少删除次数

本文涉及知识点 最大公约数 排序 LeetCode2344. 使数组可以被整除的最少删除次数 给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。 请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素&a…
阅读更多...
Apache中如何配置 ws 接口

Apache中如何配置 ws 接口

Apache中如何配置 wss 接口 在Apache中配置WebSockets的支持&#xff0c;你需要使用mod_proxy_wstunnel模块&#xff0c;该模块是Apache的一个代理模块&#xff0c;它允许你代理WebSocket请求。 以下是配置步骤的简要说明和示例&#xff1a; 确保你的Apache服务器安装了mod_…
阅读更多...
【Python小练】求斐波那契数列第n个数

【Python小练】求斐波那契数列第n个数

题目 输出斐波那契数列第n个数。 分析 首先我们要知道&#xff0c;斐波那契数列&#xff0c;这个数列从第三位开始等于前两个数的和&#xff0c;要知道数列第n个数&#xff08;n>2&#xff09;&#xff0c;就要知道其前两相的值&#xff0c;着就需要用到递归了。来看一下吧…
阅读更多...
【Java EE】多线程（二）Thread 类与常用方法

【Java EE】多线程（二）Thread 类与常用方法

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 |《MySQL探索之旅》 |《Web世界探险家》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更…
阅读更多...
【C++】：日期类的实现 -- 日期计算器

【C++】：日期类的实现 -- 日期计算器

前言 1.日期类是一种十分经典的类型。对于C的初学者&#xff0c;它能够帮助我们融会贯通许多C的基础知识&#xff0c;它涉及许多的基础语法&#xff0c;比如引用&#xff0c;函数重载&#xff0c;传值/传参返回&#xff0c;构造函数&#xff0c;运算符重载&#xff0c;const成…
阅读更多...
【Linux】详解core dump文件的作用以及用法ubuntu20.04下无法形成core dump文件的解决办法

【Linux】详解core dump文件的作用以及用法ubuntu20.04下无法形成core dump文件的解决办法

说明 从第三大点开始讲解ubuntu20.04下无法形成core dump文件的解决办法。 一、core与term的区别 在之前讲过的信号中&#xff0c;终止进程的信号的动作分为两种&#xff0c;一种是core&#xff0c;一种是term。term&#xff08;全称termination&#xff09;是直接终止进程&am…
阅读更多...
1084 外观数列（测试点3分析）

1084 外观数列（测试点3分析）

solution1 测试点3是n1的情况int转string&#xff1a;str to_string(i) string转int&#xff1a;i atoi(str.c_str()) #include<iostream> #include<string> using namespace std; int main(){int n, cnt;char x;string ans, t;cin >> t >> n;…
阅读更多...
土壤侵蚀分布数据、土壤侵蚀强度、土壤类型分布、降水量分布、坡度坡向数据、植被覆盖度、土地利用数据、土壤质地分布

土壤侵蚀分布数据、土壤侵蚀强度、土壤类型分布、降水量分布、坡度坡向数据、植被覆盖度、土地利用数据、土壤质地分布

引言 土壤侵蚀是指土壤或成土母质在外力作用下被破坏剥蚀、搬运和沉积的过程。土壤侵蚀强度是根据土壤侵蚀的实际情况&#xff0c;按轻微、中度、严重等分为不同级别。中国是世界上土壤侵蚀最严重的国家之一&#xff0c;主要发生在黄河中上游黄土高原地区、长江中上游丘陵地区和…
阅读更多...
综合性练习（后端代码练习3）——留言板

综合性练习（后端代码练习3）——留言板

目录 一、准备工作 二、约定前后端交互接口 1、需求分析 2、接口定义 &#xff08;1&#xff09;发布留言 &#xff08;2&#xff09;获取留言 三、实现服务器代码 1、lombok介绍 &#xff08;1&#xff09;引入依赖 &#xff08;2&#xff09;使用lombok &#xff…
阅读更多...
int类型的取值范围（为什么负数比正数表示的范围多一位）

int类型的取值范围（为什么负数比正数表示的范围多一位）

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;C语言基本概念 &#x1f337;追光的人&#xff0c;终会万丈光芒 目录 &#x1f3dd;1.int的基本概念&#xff1a; 空间大小&#xff1a; 有符号类型的表示形式&#xff1a; &#x1f3dd;2.…
阅读更多...
SSH远程登录实操实验！

SSH远程登录实操实验！

ssh远程登录协议&#xff1a;默认端口号22 以下实验7-2是服务端&#xff0c;7-1是客户端 服务器的相关信息&#xff1a; 服务名称&#xff1a;sshd 服务端主程序&#xff1a;/usr/sbin/sshd 服务端配置文件&#xff1a;/etc/ssh/sshd_config 客户端相关信息&#xff1a; …
阅读更多...
Java并发编程面试问题与答案

Java并发编程面试问题与答案

1. 什么是线程安全&#xff1f; 答&#xff1a; 线程安全意味着多个线程可以同时访问一个类的实例而不引起任何问题或不一致的结果。线程安全的代码会通过同步机制来确保所有线程都能正确地访问共享资源。 2. 解释Java中的synchronized关键字。 答&#xff1a; synchronized…
阅读更多...
秒杀系统的挑战和应对设计

秒杀系统的挑战和应对设计

秒杀系统是日常系统开发过程中经常遇到的场景&#xff0c;那么如何可以准备哪些措施来保证秒杀过程中系统的可用性以及一致性呢&#xff1f; 秒杀活动&#xff0c;需要满足各方的需求 作为用户&#xff0c;希望能够抢到自己中意的优惠 作为商户&#xff0c;希望券不超发&#…
阅读更多...
MATLAB 字符串

MATLAB 字符串

MATLAB 字符串 在MATLAB中创建字符串非常简单。实际上&#xff0c;我们已经使用了很多次。例如&#xff0c;您在命令提示符下键入以下内容- 示例 my_string ‘(cainiaojc.com)’ MATLAB将执行上述语句并返回以下结果 my_string (cainiaojc.com) MATLAB将所有变量视为数组&a…
阅读更多...
Macos安装OrbStack

Macos安装OrbStack

什么是OrbStack OrbStack 是一种在 macOS 上运行容器和 Linux 机器的快速、轻便和简单方法。它是 Docker Desktop 和 WSL 的超强替代品&#xff0c;所有这些都在一个易于使用的应用程序中。 在Macos M系列芯片上&#xff0c;经常遇到docker镜像不兼容的问题&#xff0c;此时使…
阅读更多...
【初识Redis】

【初识Redis】

初识Redis Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的内存数据库&#xff0c;它提供了一个高性能的键值存储系统&#xff0c;并且支持多种数据结构&#xff0c;包括字符串、哈希、列表、集合和有序集合等。Redis的特点包括&#xff1a; 内存存储&…
阅读更多...
最新文章

Copyright @ 2022~2023