uniHk

字符串（杂）

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / 字符串（杂）（共6篇）

字典树（Trie树）

字典树（Trie树，单词查找树）基本要点根节点不包含字符，除根节点外每一个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。基本操作查找、插入、删除实现过程从根节点开始...

2020-01-02

0 729

KMP+扩展KMP

KMP(三位发明者名字首字母) next数组表示t[j]以前最长相同前缀后缀若下标从0开始(以下模板就采用这种方式)，next[ i ] 表示前面下标0~i-1的字符串前缀和后缀相等的最大长度为 next[ i ] 。若下标从1开始，则next[ i ] 表示前面下标1~i - 1的字符串中...

2020-01-02

0 555

Manacher算法

洛谷-P3805板子题关键点: 要有两个字符串，且处理后的字符串长度略大于原串2倍（肯定 < 2 ...

2020-01-02

0 428

洛谷-P4287 双倍回文(Manacher)

双倍回文 Manacher算法用的还是不够熟悉啊，被卡了好久。。。一会再写个回文自动机的做法吧清晰的回文自动机写法题意：若一个回文串左半部分和有半部分分别为一个回文串，则这个回文串被称为双倍回文串(这名字有点傻呀！)。求：给定一个回文串，问最长的双倍回文串有多长。思路：由于双倍...

2020-01-02

0 521

Distinct Substrings（扩展KMP）

Distinct Substrings 写完这题发现自己曾经的扩展KMP板子（ Z Z Z函数）太laji了！现在...

2020-01-02

0 482

扩展KMP（Z algorithm）

重新记录一个板子字符串下标从 0 0 0开始（也可以很容易得改成从 ...

2020-01-02

0 362