ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共5篇）

后缀自动机

https://oj.zrt.io/problem/44 比较容易懂得文档新浪

后缀自动机

2018-12-21

0 405

bzoj3676 [Apio2014]回文串卡常+SAM+树上倍增

bzoj3676 [Apio2014]回文串 SAM+树上倍增链接 bzoj luogu 思路根据manacher可以知道，每次暴力扩展才有可能出现新的回文串。所以推出本质不同的回文串个数是O(n)级别的。每次查询一个串出现的个数。建立出parent树，一个串出现的个数就是对应pa...

后缀自动机树上倍增卡常

2019-07-13

0 708

luogu P3975 [TJOI2015]弦论 SAM

luogu P3975 [TJOI2015]弦论链接 bzoj 思路建出sam。子串算多个的，统计preant tree的子树大小，否则就是大小为1 然后再统计sam的节点能走到多少串。然后就可以在sam的贪心的走了。代码 #include <bits/stdc++.h&...

后缀自动机

2019-07-13

0 681

luogu P4248 [AHOI2013]差异 SAM

luogu P4248 [AHOI2013]差异链接 luogu 思路 \(\sum\limits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)-2*{lcp}(T_i,T_j)}\) =\(\sum\limits_{1<=i<j<...

后缀自动机

2019-07-14

0 595

luoguP4112 [HEOI2015]最短不公共子串 SAM,序列自动机，广搜BFS

luoguP4112 [HEOI2015]最短不公共子串链接 luogu loj 思路子串可以用后缀自动机，子序列可以用序列自动机。序列自动机是啥，就是能访问到所有子序列的自动机。每个点记录下一个字母最近出现的位置。不过我这里构造是\(O(n^2)\)。然后进行bfs进行广搜就行了...

后缀自动机序列自动机广搜

2019-07-14

0 623