青竹qingzhu

后缀自动机

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

全部文章 / 后缀自动机（共1篇）

P2408 不同子串个数后缀自动机做法

传送门题意给一个字符串，求它有多少个不同的子串。思路后缀数组当然是能做的，每个sa[i] - height[i]的和就是答案了。后缀自动机也可以做，后缀自动机上从起点到任意状态就是一个子串，每条路径表示的子串都不同，所以只要求出后缀自动机上从起点到其它点的路径条数就是不同子串的个数。 #...

2020-07-13

0 706