UVA1449 Dominating Patterns 题解
UVA1449 Dominating Patterns 题解
板子题诶。
解法
AC 自动机模板题,因为数据范围比较小,所以不加拓扑排序优化建图即可通过本题。这里简单介绍一下拓扑排序优化建图。
在查找时,每次都暴力的条 f a i l fail fail 指针是很消耗时间的,查找到了一个字符串可能意味着找到了多个字符串,例如我们有两个模式串 bc 和 abc,我们找到了串 abc,这同时意味着我们找到了串 bc,如果每次都去跳失配边的话效率过低,我们可以在找到一个模式串后打标记,最后进行拓扑排序求得最后的答案。
为什么可以使用拓扑排序?
因为失配边都是有向边,而失配边的起点一定比终点深度要深,而且不会存在自环。所以所有失配边所构成的图是一个有向无环图。
另外,这里建图不用真的把边都建出来,统计一下入度就行。
代码
#include<bits/stdc++.h>
namespace fast_IO
{/*** 快读快写。*/
};
using namespace fast_IO;
class AC_auto
{
private:#define LEN 1000001#define N 200int a[LEN][26],val[LEN],flag[LEN],fail[LEN],ind[LEN],cnt,tmp;int ans[N],map[N];std::deque<int> q;
public:inline AC_auto(){memset(fail,0,sizeof(fail)),memset(val,0,sizeof(val)),memset(flag,0,sizeof(flag));memset(a,0,sizeof(a)),memset(ind,0,sizeof(ind));memset(ans,0,sizeof(ans)),memset(map,0,sizeof(map));cnt=1;}inline void clear(){for(int i=0;i<=cnt;i++) memset(a[i],0,sizeof(a[i])),val[i]=flag[i]=fail[i]=ind[i]=0;memset(ans,0,sizeof(ans)),memset(map,0,sizeof(map));cnt=1;}inline void build(){for(int i=0;i<26;i++) a[0][i]=1;q.push_back(1);while(!q.empty()){tmp=q.front();q.pop_front();for(int i=0;i<26;i++)if(a[tmp][i])fail[a[tmp][i]]=a[fail[tmp]][i],ind[fail[a[tmp][i]]]++,q.push_back(a[tmp][i]);else a[tmp][i]=a[fail[tmp]][i];}}inline void add(std::string st,int pos){int now=1;for(int i=0;i<st.size();i++){if(!a[now][st[i]-'a']) a[now][st[i]-'a']=++cnt;now=a[now][st[i]-'a'];}if(!flag[now]) flag[now]=pos;map[pos]=flag[now];}inline void ask(std::string st){int now=1;for(int i=0;i<st.size();i++) now=a[now][st[i]-'a'],val[now]++;}inline void topo_sort(){for(int i=1;i<=cnt;i++) if(!ind[i]) q.push_back(i);while(!q.empty()){tmp=q.front(),q.pop_front();ans[flag[tmp]]=val[tmp],val[fail[tmp]]+=val[tmp];if(!(--ind[fail[tmp]])) q.push_back(fail[tmp]);}}inline std::vector<int> output(const int l,const int r){std::vector<int> ret;int maxi=0;for(int i=l;i<=r;i++)if(ans[map[i]]>maxi) maxi=ans[map[i]],ret.clear(),ret.push_back(i);else if(ans[map[i]]==maxi) ret.push_back(i);out<<maxi<<'\n';return ret;}
};
AC_auto ac_auto;
int n;
std::string s,t[200];
std::vector<int> v;
int main()
{while(1){in>>n;if(n==0) break;ac_auto.clear();for(int i=1;i<=n;i++) in>>t[i],ac_auto.add(t[i],i);ac_auto.build(),in>>s,ac_auto.ask(s),ac_auto.topo_sort(),v=ac_auto.output(1,n);for(int i=0;i<v.size();i++) out<<t[v[i]]<<'\n';}fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);return 0;
}
相关文章:
UVA1449 Dominating Patterns 题解
UVA1449 Dominating Patterns 题解 板子题诶。 解法 AC 自动机模板题,因为数据范围比较小,所以不加拓扑排序优化建图即可通过本题。这里简单介绍一下拓扑排序优化建图。 在查找时,每次都暴力的条 f a i l fail fail 指针是很消耗时间的&…...
【C语言】数据结构#实现堆
目录 (一)堆 (1)堆区与数据结构的堆 (二)头文件 (三)功能实现 (1)堆的初始化 (2)堆的销毁 (3)插入数据 …...
AES加密中的CBC和ECB
目录 1.说明 2.ECB模式(base64) 3.CBC模式 4.总结 1.说明 AES是常见的对称加密算法,加密和解密使用相同的密钥,流程如下: 主要概念如下: ①明文 ②密钥 用来加密明文的密码,在对称加密算…...
【C++】类和对象(四)
前言:在类和对象中,我们走过了十分漫长的道路,今天我们将进一步学习类和对象,类和对象这块荆棘地很长,各位一起加油呀。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:高质量&a…...
XGB-5: DART Booster
XGBoost 主要结合了大量的回归树和一个小的学习率。在这种情况下,早期添加的树是重要的,而晚期添加的树是不重要的。 Vinayak 和 Gilad-Bachrach 提出了一种将深度神经网络社区的 dropout 技术应用于梯度提升树的新方法,并在某些情况下报告了…...
HiveSQL——不使用union all的情况下进行列转行
参考文章: HiveSql一天一个小技巧:如何不使用union all 进行列转行_不 union all-CSDN博客文章浏览阅读881次,点赞5次,收藏10次。本文给出一种不使用传统UNION ALL方法进行 行转列的方法,其中方法一采用了concat_wsposexplode()方…...
Python环境下基于指数退化模型和LSTM自编码器的轴承剩余寿命预测
滚动轴承是机械设备中关键的零部件之一,其可靠性直接影响了设备的性能,所以对滚动轴承的剩余使用寿命(RUL)进行预测是十分必要的。目前,如何准确地对滚动轴承剩余使用寿命进行预测,仍是一个具有挑战的课题。对滚动轴承剩余寿命评估…...
无人机竞赛视觉算法开发流程开源计划(询问大家意见)
本科中参加过一系列的无人机机器人竞赛,像电赛、工训赛、机器人大赛这些,有一些比较常用的方案打算开源一下。现在读研了,也算是对本科的一个总结,但是还是想看看大家意见,大家有什么需求可以在评论区说,我…...
DMA直接内存访问,STM32实现高速数据传输使用配置
1、DMA运用场景 随着智能化、信息化的不断推进,嵌入式设备的数据处理量也呈现指数级增加,因此对于巨大的数据量处理的情况时,必须采取其它的方式去替CPU减负,以保证嵌入式设备性能。例如SD卡存储器和音视频、网络高速通信等其它情…...
Web安全研究(六)
文章目录 HideNoSeek: Camouflaging(隐藏) Malicious JavaScript in Benign ASTs文章结构Introjs obfuscationmethodologyExample HideNoSeek: Camouflaging(隐藏) Malicious JavaScript in Benign ASTs CCS 2019 CISPA 恶意软件领域,基于学习的系统已经非常流行&am…...
python3 中try 异常调试 raise 异常抛出
一、什么是异常? 异常即是一个事件,该事件会在程序执行过程中发生,影响了程序的正常执行。 一般情况下,在Python无法正常处理程序时就会发生一个异常。 异常是Python对象,表示一个错误。 当Python脚本发生异常时我…...
Java中的序列化是什么?如何实现对象的序列化和反序列化?请解释Serializable接口的作用是什么?请解释transient关键字的作用是什么?为什么会使用它?
Java中的序列化是指将对象转换为字节序列的过程,以便可以在网络上传输或将其保存到持久存储介质中。反序列化则是将字节序列重新转换回对象的过程。Java提供了一种称为序列化(Serialization)的机制来实现对象的序列化和反序列化。 要实现对象…...
二维差分---三维差分算法笔记
文章目录 一.二维差分构造差分二维数组二维差分算法状态dp求b[i][j]数组的二维前缀和图解 二.三维前缀和与差分三维前缀和图解:三维差分核心公式图解:模板题 一.二维差分 给定一个原二维数组a[i][j],若要给a[i][j]中以(x1,y1)和(x2,y2)为对角线的子矩阵中每个数都加上一个常数…...
D. Divisible Pairs
思路:我们预处理出每个数分别摸上xy的值,用map存一下,然后遍历每个数,如果a b是x的倍数的话,那么他们模x的值相加为x,如果a - b是y的倍数的话,那么他们的模y的值相等。 代码: voi…...
【教程】Kotlin语言学习笔记(二)——数据类型(持续更新)
写在前面: 如果文章对你有帮助,记得点赞关注加收藏一波,利于以后需要的时候复习,多谢支持! 【Kotlin语言学习】系列文章 第一章 《认识Kotlin》 第二章 《数据类型》 文章目录 【Kotlin语言学习】系列文章一、基本数据…...
react 插槽
问题开发当中会经常出现组件十分相似的组件,只有一部分是不同的 解决: 父组件:在引用的时候 import { Component } from "react"; import Me from "../me";const name <div>名称</div> class Shoop extends Compone…...
Linux运用fork函数创建进程
fork函数: 函数原型: pid_t fork(void); 父进程调用fork函数创建一个子进程,子进程的用户区父进程的用户区完全一样,但是内核区不完全一样;如父进程的PID和子进程的PID不一样。 返回值: RETURN VALUEO…...
Pytest测试技巧之Fixture:模块化管理测试数据
在 Pytest 测试中,有效管理测试数据是提高测试质量和可维护性的关键。本文将深入探讨 Pytest 中的 Fixture,特别是如何利用 Fixture 实现测试数据的模块化管理,以提高测试用例的清晰度和可复用性。 什么是Fixture? 在 Pytest 中&a…...
设计模式-职责链模式Chain of Responsibility
职责链模式 一、原理和实现二、实现方式1) 使用链表实现2) 使用数组实现3) 扩展 作用:复用和扩展,在实际的项目开发中比较常用。在框架开发中,我们也可以利用它们来提供框架的扩展点,能够让框架的使用者在不修改框架源码的情况下&…...
书生浦语大模型实战营-课程作业(3)
下载sentence_transformer的代码运行情况。sentence_transformer用于embedding(转向量) 本地构建持久化向量数据库。就是把txt和md文件抽取出纯文本,分割成定长(500)后转换成向量,保存到本地,称…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
MySQL体系架构解析(三):MySQL目录与启动配置全解析
MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录,这个目录下存放着许多可执行文件。与其他系统的可执行文件类似,这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中,用…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...
初级程序员入门指南
初级程序员入门指南 在数字化浪潮中,编程已然成为极具价值的技能。对于渴望踏入程序员行列的新手而言,明晰入门路径与必备知识是开启征程的关键。本文将为初级程序员提供全面的入门指引。 一、明确学习方向 (一)编程语言抉择 编…...
开疆智能Ethernet/IP转Modbus网关连接鸣志步进电机驱动器配置案例
在工业自动化控制系统中,常常会遇到不同品牌和通信协议的设备需要协同工作的情况。本案例中,客户现场采用了 罗克韦尔PLC,但需要控制的变频器仅支持 ModbusRTU 协议。为了实现PLC 对变频器的有效控制与监控,引入了开疆智能Etherne…...
