搜索结果
查询Tags标签： 失配，共有 7条记录-
字符串基础：hash，kmp，trie
三个很基础的板子放到一块。发现原来没有位置放了于是现开一个。Hashhash的思想是把一个字符串拍成一个数存储，这样就能快速比较两个字符串是否相同。 大概的方法：我们选取一个合适的进制数（比如131这样的质数）和一个较大的模数。 将这个字符串看作一个p进制数（因为每…
2022/9/3 23:22:45 人评论 次浏览 -
捉迷藏
给定一个有向无环图 最多找到多少个点 并且这些点相互不连通有向无环图的最小路径点覆盖=n-拆点二分图的最大匹配(路径不能相交) 每个左部点的失配代表该点没有出边 所以代表着一条路径的终点 终点最少,失配点最少,路径覆盖就最少 最小可重点覆盖(路径可以相交) 先传递闭包…
2022/2/11 23:44:25 人评论 次浏览 -
【数据结构梳理04】串的模式匹配——KMP算法
一、串的模式匹配 设有两个串S和pat，若在S中查找是否有与pat相同的子串，则称串S为目标，称pat为模式，串的模式匹配即为查找模式串在目标串中的匹配位置的运算。（1）朴素的模式匹配（B-F算法） 朴素的模式匹配想法十分简单粗暴：将pat中的每个字符依次与S中的字符比较，…
2021/12/5 17:17:19 人评论 次浏览 -
【数据结构梳理04】串的模式匹配——KMP算法
一、串的模式匹配 设有两个串S和pat，若在S中查找是否有与pat相同的子串，则称串S为目标，称pat为模式，串的模式匹配即为查找模式串在目标串中的匹配位置的运算。（1）朴素的模式匹配（B-F算法） 朴素的模式匹配想法十分简单粗暴：将pat中的每个字符依次与S中的字符比较，…
2021/12/5 17:17:19 人评论 次浏览 -
Codeforces461E Appleman and a Game 做题心得
目录思维过程思路总结代码 躺在床上睡不着，想这个题，突然有了一个对的思路，把自己吓醒 思维过程 首先我们要考虑的是，假设 \(s\) 已知，Appleman 的策略是什么 我们发现他的策略非常简单，就是能匹配就继续匹配，直到不能再匹配了，才划分一下 道理也很简单，现在不划…
2021/6/24 23:28:37 人评论 次浏览 -
【YBTOJ】【Luogu P2444】[POI2000]病毒
链接： 洛谷 题目大意： 构造一个无限长的文本串，使得此串不能被匹配。 正文： 好题。我的一开始的思路是，像 01trie 求最大异或那样跑 trie，然后跳失配指针判断合法。但显然假了。 于是得深度思考题意，“不能被匹配”说明跑 trie 时尽量失配，那么在求出失配指针后被…
2021/6/3 18:22:48 人评论 次浏览 -
【学习笔记】Berlekamp-Massey算法
Berlekamp_Massey算法是用来在\(O(n^2)\)时间内求解长度为\(n\)的数列的最短递推式算法。 如果我们已经知道前\(i\)项的递推式\(R,\)它不满足第\(n\)项，我们如何来调整它使得它满足第\(n\)项？ 考虑往\(R\)上面加上一个递推式\(F.\) 设\(\Delta_{i}\)表示第\(i\)个递推式…
2021/5/2 12:25:09 人评论 次浏览
