AC自动机(简单模板)

AC自动机,就相当于是在字典树上用kmp。next数组回退的位置为最大匹配字符串在字典树上的节点位置。

在获取字典树上的next数组的时候用的是BFS每次相当与处理的一层。

下图中红线为,可以回退的位置,没有红线的节点回退的位置都是虚拟原点。

int n, m;
int o[N];
int tr[N][26], cnt[N], idx;
char str[N];
int q[N], ne[N];

inline void insert() { // 正常的字典树插入板子
	int p = 0;
	for(int i = 0; str[i]; i ++) {
		int t = str[i] - 'a';
		if(!tr[p][t]) tr[p][t] = ++ idx;
		p = tr[p][t];
	}
	cnt[p] ++; // 记录当前字符串出现的次数
}

void build() {
	int  hh = 0, tt = -1;

	for(int i = 0; i < 26; i ++) // 因为第二层的所有字符串长度为一,next值肯定为1,直接入队即可
		if(tr[0][i])
			q[++ tt] = tr[0][i];

	while(hh <= tt) {
		int t = q[hh ++];
		for(int i = 0; i < 26; i ++) {
			int p = tr[t][i];
			if(!p) tr[t][i] = tr[ne[t]][i]; // 匹配失败,则回退,路径压缩过,一次回退即可
			else {
				ne[p] = tr[ne[t]][i]; // 记录ne数组,顺便压缩路径
				q[ ++ tt] = p;
			}
		}
	}
}

inline void sovle() {
	idx = 0;
	cin >> n;
	for(int i = 0; i < n; i ++) {
		cin >> str;
		insert(); // 将所有字符串全都插入字典树
	}
	build(); // 获取next数组
	cin >> str;
	int res = 0;
	int s = 0;
	for(int i = 0, j = 0; str[i]; i ++) { // 同时匹配字典树中所有的字符串
		int t = str[i] - 'a';
		j = tr[j][t];
		int p = j;
		while(p && cnt[p] != 0) { // 线性匹配,这里的第二个条件是一个优化,只有在每个字符串只记录一次的前提下使用
			res += cnt[p]; // 记录出现过的字符串的个数
			cnt[p] = 0; // 因为每个字符串只计算一次,所以要清空
			p = ne[p]; // 回退
		}
	}
	cout << res << endl;
}

与上一题不一样的只有一小部分,这题中,每个字符串可重复记录,所以就不能加上那个线性优化,还需要记录每个字符串出现的次数即可。

int n, m;
int o[N];
int tr[N][26], cnt[N], idx;
string sr[200];
char str[N];
int q[N], ne[N], st[N];

inline void insert(string s) {
	int p = 0;
	for(int i = 0; i < s.size(); i ++) {
		int t = s[i] - 'a';
		if(!tr[p][t]) tr[p][t] = ++ idx;
		p = tr[p][t];
	}
	cnt[p] ++;
}

void build() {
	int  hh = 0, tt = -1;

	for(int i = 0; i < 26; i ++)
		if(tr[0][i])
			q[++ tt] = tr[0][i];

	while(hh <= tt) {
		int t = q[hh ++];
		for(int i = 0; i < 26; i ++) {
			int p = tr[t][i];
			if(!p) tr[t][i] = tr[ne[t]][i];
			else {
				ne[p] = tr[ne[t]][i];
				q[ ++ tt] = p;
			}
		}
	}
}

int query(string s) { // 与插入差不多 些许操作不同
	int p = 0;
	for(int i = 0; i < s.size(); i ++) {
		int t = s[i] - 'a';
		if(!tr[p][t]) return 0;
		p = tr[p][t];
	}
	return st[p];
}

inline void sovle() {

	while(cin >> n, n) {
		memset(tr, 0, sizeof tr);
		memset(cnt, 0, sizeof cnt);
		memset(ne, 0, sizeof ne);
		memset(st, 0, sizeof st);
		idx = 0;
		for(int i = 0; i < n; i ++) {
			cin >> sr[i];
			insert(sr[i]);
		}
		build();
		cin >> str;
		int res = 0;
		int s = 0;
		for(int i = 0, j = 0; str[i]; i ++) {
			int t = str[i] - 'a';
			j = tr[j][t];
			int p = j;
			while(p) {
				st[p] += cnt[p]; // 记录该字符串出现的次数
				s = max(st[p], s); // 因为要求出来最多出现的字符串的次数
				p = ne[p]; // 回退
			}
		}
		cout << s << endl;
		for(int i = 0; i < n; i ++) {
			int k = query(sr[i]); // 字典树的查询操作,查询st数组。
			if(s == k) cout << sr[i] << endl; // 是最大的直接输出。
		}
	}
}

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

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

相关文章

Nginx 配置错误导致的漏洞

目录 1. CRLF注入漏洞 Bottle HTTP头注入漏洞 2.目录穿越漏洞 3. http add_header被覆盖 本篇要复现的漏洞实验有一个网站直接为我们提供了Docker的环境&#xff0c;我们只需要下载下来就可以使用&#xff1a; Docker环境的安装可以参考&#xff1a;Docker安装 漏洞环境的…

Android笔记(十五):JetPack Compose的附带效应(二)-produceState和derivedStateOf

在本笔记中&#xff0c;将结合实例介绍produceState和derivedStateOf两个可组合函数。它们分别实现状态的转换。 &#xff08;1&#xff09;produceState将非Compose状态转换虫Compose状态 &#xff08;2&#xff09;derivedStateOf将多个状态转换成其他状态。 一、produceSta…

NFC技术简介

NFC简介 NFC(近场通信&#xff0c;Near Field Communication&#xff09;是一种短距高频的无线电技术&#xff0c;由非接触式射频识别(RFID)演变而来。 NFC工作频率为13.56Hz&#xff0c;通常只有在距离不超过4厘米时才能启动连接&#xff0c;其传输速度有106 Kbit/秒、212 Kb…

「Whale 帷幄」连续入选科技榜单,AGI 冲击波正在加速行业洗牌

以 AGI 为底座&#xff0c;品牌 MarTech 正在经历一场前所未有的深度变革。 近日&#xff0c;弯弓研究院发布「中国 MarTech 500 强榜单」&#xff0c;以 2023 中国营销技术&#xff08;MarTech&#xff09;生态为研究对象&#xff0c;洞察行业现象与未来趋势。作为品牌数字化…

视频剪辑新招:批量随机分割,分享精彩瞬间

随着社交媒体的普及&#xff0c;短视频已经成为分享生活、交流信息的重要方式。为制作出吸引的短视频&#xff0c;许多创作者都投入了大量的时间和精力进行剪辑。然而&#xff0c;对于一些没有剪辑经验的新手来说&#xff0c;这个过程可能会非常繁琐。现在一起来看云炫AI智剪批…

AI制作的《大多数普通女孩的一生》——公开教程和工作流

内容来源&#xff1a;JiamigouCn ​这周由AI制作的《大多数普通女孩的一生》&#xff0c;在抖音爆火&#xff0c;获得新华网转发。到目前为止&#xff0c;全网还没有公开教程和工作流&#xff0c;需要花费800-2000购买。 本着AI社区共享原则&#xff0c;我委托公众号“楚思智能…

Debian12试用报告

环境: win11vbox 虚拟机 网络: host-only访问局域网 nat 访问外网, 配置为dhcp动态获取ip 遇到的问题: 偶尔卡死: nat每次开机都不生效, 外网无法访问; 开机后 重启网络可解决 sudo /etc/init.d/networking restart host-only倒是没问题, 内网正常访问 vim9还是用不习…

ubuntu22.04 arrch64版在线安装java环境

脚本 #安装java#!/bin/bashif type -p java; thenecho "Java has been installed."else#2.Installed Java , must install wgetwget -c https://repo.huaweicloud.com/java/jdk/8u151-b12/jdk-8u151-linux-arm64-vfp-hflt.tar.gz;tar -zxvf ./jdk-8u151-linux-arm6…

【Spring集成MyBatis】核心配置文件

文章目录 1. typeHandlers标签2. plugins标签通过PageHelper的API获取分页的信息 1. typeHandlers标签 可以重写类型处理器&#xff0c;或创建类型处理器来处理不支持/非标准的类型。选择性地将它映射到一个JDBC类型&#xff1a;如Java中的Date类型&#xff0c;将其存放到数据…

“土味出海”,屡试不爽!短剧出海引来新一轮爆发?

土味和“钱途”并存的短剧不仅在国内迅猛爆发&#xff0c;今年下半年以来海外市场多部爆火短剧出现&#xff0c;“短剧出海”的话题热度不断攀升&#xff0c;丝毫不差2021年网文出海的盛况。 “霸总的爱&#xff0c;日入千万刀”&#xff0c;是真实存在的&#xff01; 据统计…

快手ConnectionError

因为运行的程序被中断导致 top然后查看站用处内存高的accelerate kill进程号 9回车

概要设计文档案例分享

1引言 1.1编写目的 1.2项目背景 1.3参考资料 2系统总体设计 2.1整体架构 2.2整体功能架构 2.3整体技术架构 2.4运行环境设计 2.5设计目标 3系统功能模块设计 3.1个人办公 4性能设计 4.1响应时间 4.2并发用户数 5接口设计 5.1接口设计原则 5.2接口实现方式 6运行设计 6.1运行模块…

图像标记上线,描点信息尽在掌握丨三叠云

图像标记 路径 表单设计 >> 组件 >> 增强组件 功能简介 「图像标记」字段是「增强字段」类型字段。用户通过上传图片的方式构建一个背景图片&#xff0c;并在构建的图片背景上添加描点信息。搭配「仪表盘」中的「图像轨迹」&#xff0c;可绘制出相应的数据轨迹…

MySQL数据库入门到大牛_基础_14_视图及基本操作

本章开始将会介绍表之外的数据库对象。 文章目录 1. 常见的数据库对象2. 视图概述2.1 为什么使用视图&#xff1f;2.2 视图的理解 3. 创建视图3.1 创建单表视图3.2 创建多表联合视图3.3 基于视图创建视图 4. 查看视图5. 更新视图的数据5.1 一般情况5.2 不可更新的视图 6. 修改…

马斯克星链与芯事:30亿美元炸出卫星互联网革命,GPU算力创无限可能

★卫星互联网&#xff1b;算力&#xff1b;卫星通信&#xff1b;互联网&#xff1b;低轨卫星互联网&#xff1b;5G基础设施&#xff1b;GPT-4 Turbo&#xff1b;算力&#xff1b;地面通信&#xff1b;液冷&#xff1b;水冷&#xff1b;AI服务器&#xff1b;东数西算&#xff1b…

收藏这几个开源库,写css你会笑出声

你是否遇到过写css没灵感&#xff0c;写不出酷炫的效果&#xff0c;那这篇文章你一定要看完。知道这几个开源库&#xff0c;它能让你写出炸天的效果并且有效地增加你的摸鱼时长。 1.CSS Inspiration 网址&#xff1a;https://chokcoco.github.io/CSS-Inspiration/#/ CSS Insp…

时间序列分析算法的概念、模型检验及应用

时间序列分析是一种用于研究随时间变化的数据模式和趋势的统计方法。这类数据通常按照时间顺序排列&#xff0c;例如股票价格、气温、销售额等。时间序列分析的目标是从过去的观测中提取信息&#xff0c;以便预测未来的趋势。 以下是关于时间序列分析的一些重要概念、模型检验…

[Android]使用Retrofit进行网络请求

以下是使用 Retrofit 发送 POST 请求获取分页城市列表的 Kotlin 代码示例 1.在你的 build.gradle 文件中添加 Retrofit 和 Gson 的依赖 dependencies {......implementation("com.squareup.retrofit2:retrofit:2.9.0")implementation("com.squareup.retrofit2…

在Linux服务器部署爬虫程序?大佬只需七步!

之前在某乎上看见一篇关于《为什么很多程序员都建议使用 Linux》的文章&#xff0c;结合我自身关于Linux的使用经验。心血来潮得写了一段关于我在Linux系统部署爬虫程序的心得&#xff0c;希望结识更多的爬虫技术大佬&#xff0c;一起游弋在代码世界中。 根据我多年在Linux上部…

基于C#实现Dijkstra算法

或许在生活中&#xff0c;经常会碰到针对某一个问题&#xff0c;在众多的限制条件下&#xff0c;如何去寻找一个最优解&#xff1f;可能大家想到了很多诸如“线性规划”&#xff0c;“动态规划”这些经典策略&#xff0c;当然有的问题我们可以用贪心来寻求整体最优解&#xff0…