泪痕 @ 铁憨憨
辗转当作浮生妖,流离惊似尘世鬼
NOI2016 优秀的拆分 NOI2016 优秀的拆分
摘要 人生第二道黑题~ 如果一个字符串可以被拆分为 AABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串 aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符串拆分成
2019.04.10
[NOI2011] 阿狸的打字机 [NOI2011] 阿狸的打字机
摘要 好一个 AC 自动机 + 树状数组的题 打字机上只有 28 个按键,分别印有 26 个小写英文字母和’B’、’P’两个字母。经阿狸研究发现,这个打字机是这样工作的: 输入小写字母,打字机的一个凹槽中会加入这个字母 (这个字母加在
2019.04.10
[NOI2014] 动物园 [NOI2014] 动物园
摘要 题意:对字符串的每个前缀求长度小于等于一半的 的个数 许多题解里都说可以在求 的时候顺便求,笔者没有想到这个思路。根据 的树形结构,其实相当于在树上找到根结点路径上编号小于等于一半的
2019.04.10
[POI2006]OKR-Periods of Words [POI2006]OKR-Periods of Words
摘要 题意:求一个串所有前缀的最长周期之和。这里的周期是非严格周期,不能为自身 即求最短 border,那么 就是最长周期。注意到 数组求的是最长 ,而
2019.04.10
字符串小结 字符串小结
KMP 复杂度的证明咕咕 一道题 给一个串, 支持插入删除最后面的字符, 求循环节的长度。这里的循环节是整个串的循环节,任意一个都可以. 求循环节就相当于求 Next 指针,考虑 Next 指针的构建过程。当前的 Next 指针是建立在
2019.02.12
KMP 算法 KMP 算法
摘要 用于字符串匹配,在 O(n) 复杂度内完成匹配。 算法思想对于朴素算法,当 即匹配失败时,是将整个 S 向后移动一位,复杂度 O(mn)。这种算法的缺点在于,移动一
2019.02.12
字典树 |TRIE 字典树 |TRIE
字典树 |TRIE简介字典树,其实就是一颗树。但是这颗树就像字典一样,能迅速匹配字典中的字符串。 基本性质: 根结点不包含字符,除根结点外每一个结点都只包含一个字符。 从根结点到某一结点,路径上经过的字符连接起来,为该结点对应的字符串。
2018.10.01
后缀数组 后缀数组
摘要 后缀数组由 Manber & Myers 在 1990 年首先提出《Suffix arrays: a new method for on-line string searches》,用以替代后缀树,并且改进了存储空间的需求。
2018.10.01
字典树 字典树
简介字典树,英文名Trie。顾名思义,就是一个像字典一样的树。先放一张图: 可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子, 表示的就是字符串 caa。 结
2018.10.01
AC 自动机 ·Automaton AC 自动机 ·Automaton
摘要 之前洛谷日报上发了一篇《强势图解 AC 自动机》,现在复习一下,重新整理思路 2019.6.16:编入精选文章 前言声明:代码部分的字符串都以 1 为起点 另外,有小伙伴问我 GIF 图片是怎么生成的。在此我以个人名誉担保—— 这
2018.10.01