首页 > 其他分享 >【题解】 Pattern Matching in A Minor "Low Space" CCPC Mianyang 2022

【题解】 Pattern Matching in A Minor "Low Space" CCPC Mianyang 2022

时间:2023-08-07 18:33:10浏览次数:65  
标签:Mianyang Space Pattern 20000 Low 题解

https://vjudge.net/contest/573644#problem/K

字符串匹配,但卡空间。

考虑哈希做法,不妨把 \(s\) 每 \(20000\) 个字符哈希成一个字符,于是 \(s\) 长度只有 \(500\),可以跑个 KMP。

于是对于 \(t\),我们只需要同时维护 \(20000\) 个 KMP 的指针。

但如果字符串长度不是 \(20000\) 的倍数怎么办呢?注意到我们可以手动 hash 匹配最后一个不完整区间,gg!

复杂度线性,正确性不好说,因为要 hash!

标签:Mianyang,Space,Pattern,20000,Low,题解
From: https://www.cnblogs.com/imakf/p/17612260.html

相关文章

  • P9498 「RiOI-2」equals题解
    题目传送门:P9498「RiOI-2」equals-洛谷|计算机科学教育新生态(luogu.com.cn)这是洛谷月赛Div.2T3,由于我比较菜,只能赛场上切到T3(T4是黑。),开题我们很容易就看出这道题首先需要初始化每个点到根节点的最短路,而且边权都为1,所以我们先无脑打一个堆优化的dijkstra,剩下的就是处......
  • P1005 [NOIP2007 提高组] 矩阵取数游戏题解
    题面传送门:P1005[NOIP2007提高组]矩阵取数游戏-洛谷|计算机科学教育新生态(luogu.com.cn)分析题目可知,这道题是一道求最值的问题,第一次看题没有认真读题,以为是每次只在某一行中选一个数,于是想了半天无果。重新读题才发现每次需要每行都取,那么这就很简单了,相当于在每一行......
  • 洛谷 P1336 最佳课题选择 题解
    P1336最佳课题选择题解状态:考虑\(f_{i,j}\)表示前\(i\)种论文里面,一共写了\(j\)篇,的最少花费时间。转移策略:我们一次考虑每一种论文写多少篇。假设写\(k\)篇,\(k\in[0,j]\cap\mathbb{Z}\),有转移方程:\[f_{i,j}=min(f_{i-1,j-k}+cost(i,k)),k\in[0,j]\cap\mathbb{......
  • RTSP/Onvif视频服务器LntonNVR(源码版)视频平台无法通过Onvif控制摄像头云台的问题解决
    LntonNVR视频边缘计算网关平台是我们推出的软硬一体的视频平台,既有软件版本,又有硬件版本。LntonNVR与摄像头连接时,可以通过平台自带的Onvif探测进行设备探测、连接,还能实现对摄像头的PTZ云台控制,包括镜头转向、变焦等操作。通过Onvif控制云台是非常实用的功能,在很多用户实际项目中......
  • 国标GB28181视频平台LntonGBS(源码版)国标平台出现录像无法播放并存在RTMP重复推流现象
    LntonGBS国标视频云服务通过支持国标GB28181协议,实现了设备接入、实时监控直播、录像、语音对讲、云存储、告警、级联等功能。同时,它还支持将接入的视频流以多种格式(包括RTSP、RTMP、FLV、HLS、WebRTC)进行全终端、全平台分发,实现了无插件播放在Web浏览器、手机浏览器、微信端、PC客......
  • zookeeper常见问题解决
     注意:自zk3.5.5版本以后,已编译的jar包,尾部有bin标识,应该使用的是apache-zookeeper-3.x.x-bin.tar.gz 错误一:Startingzookeeper…FAILEDTOSTART版本问题,自3.5以上的版本,随着版本的更新,3.5版本以后的压缩包分成了两种我们需要使用文件名带有bin的那个压缩包,例如:ap......
  • [ABC313] C~E 题解
    [ABC313]C~E题解C-ApproximateEqualization2让所有的数字都尽量接近平均数,先算出平均数,然后把所有数字分成两份,一份要加,一份要减,因为平均数有余数,余数肯定给最大的几个,所以这样计算总共需要加减多少个,然后在加减里面取\(\max\)即可。时间复杂度:\(O(n\logn)\)#include......
  • 题解 P6831 - [IOI2020] 嘉年华奖券
    小清新IOI题。首先考虑怎么求出答案。等价于我选择\(\dfrac{nk}{2}\)个数令它们系数为\(1\),再选\(\dfrac{nk}{2}\)个数令它们系数为\(-1\),最大化每个数的值乘以系数之和,并且要求每个奖券选择的数的个数恰好是\(k\)个。考虑先令每个奖券的前\(k\)个数系数为\(-1\),然......
  • HHKB2020 D 题解
    problem&blog。特判一下\(a+b>n\)时为\(0\)。正难则反,计算重叠的方案数。重叠即\(x,y\)轴均有交集,于是转化为两条线段相交的方案数(两条线段认为是不同的)。正难则反,计算不相交的方案数。第一条线段有\((n-b+1)-a+1=n-a-b+2\)种可能,第二条有\((n-a-b+1)\)种可能,故方案......
  • 题解 [POI2012] OKR-A Horrible Poem
    题目链接询问循环节的“模板题”?首先,有一个经典结论:若存在一长度为\(len\)的循环节,则\(s[l\simr-len]=s[l+len\simr]\),简单来说就是利用移位,说明是否是循环节。有了这个结论,再使用字符串哈希,我们就可以做到\(O(1)\)判断。因为:字符串长度=循环节长度\(\times\)循环......