nihility
  文章分类
数据结构 5 字符串 3 图论 2 动态规划 1 Golang 3
后缀自动机 后缀自动机
后缀自动机，又称为SAM，是个有限状态自动机，我们可以把它看作一张有向拓扑图。由一个起点、若干终点组成。原串的所有子串和从SAM起点开始的所有路径一一对应，不重不漏。所有到达终点的路径就是原串的一个后缀。其中，每个点包含若干子串，每个子串
2022-07-27 字符串
后缀自动机
后缀数组 后缀数组
后缀数组常用的算法有两种，一种是倍增，一种是DC3，其中DC3是线性的，不过代码更恶心，常数也比较大，这里本人就先讲一下倍增的做法，虽然时间复杂度略差，不过还是很好用的。
2022-07-27 字符串
后缀数组
字符串哈希 字符串哈希
哈希是一种映射方法，我们用哈希把万物映射成一个整数值，字符串哈希就是把字符串映射为一个整数值，这样我们就能快速判断两个字符串是否相同。字母集$T$就是我们用到所有字母的集合，$|T|$就是其大小。$H$为哈希函数,$S$为字符串，$n$为
2022-06-20 字符串
字符串哈希