ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共1篇）

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

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

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

2019-07-14

0 623