ST表

ST表

简介 给定一个长度为 n 的数组,支持 O(1) 查询区间最值。 使用前,调用 init() 函数初始化 ST,然后使用 query() 函数查询区间最值。 当前代码实现区间最小值问题,区间的最大值,最大公约数等均可以查询。 原理 预处理出原区间内长度为 1, 2, 4, \cdots, 2^k 的子区间的答案,此预处理的复杂度为 O(n \log n)。 ...
后缀数组

后缀数组

简介 给定一个 0-Based 字符串 Str,将它的所有后缀进行排序。 数组 sa[i] 中保存排名第 i 的后缀的在字符串的那个位置,数组 rank[i] 表示从位置 i 开始的子串的排名。 数组 height[i] 表示排名第 i 的字符串和排名第 i+1 的字符串的公共前缀长度。 代码 namespace SuffixArray{ const...
AC自动机

AC自动机

简述 处理多模式串匹配问题,初始化后(init),先插入所有模式串(insert),然后构建AC自动机(build),最后进行匹配(next)。 假设模式串集合为 {S},目标串为 T,那么算法复杂度为 O(Simga_i |S_i| + |T|)。 原理 等待填坑… 代码 class AhoCorasiek{ protected: co...