• https://uoj.ac/problem/131

显然我们只需要在后缀树上 dp 即可，比较容易的写法是逆序构造 sam。https://www.luogu.com.cn/record/196889119

另外因为后缀树组的 height 数组上建笛卡尔树叶可以构造出 fail 树等价结构，而 height 数组恰好对应了 n-1 个内点，height 对应后缀共享的最长公共前缀 len，n 个空儿子恰好对应了 |endpos| = 1 的叶子结点。(https://github.com/981377660LMT/algorithm-study/blob/585e0b2b800fa08ae1fc4e89fd53fa64a2683510/17_%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D/%E5%90%8E%E7%BC%80%E6%A0%91/SuffixTree.go

https://www.luogu.com.cn/record/196821208

另外此处也可以不显示构造出后缀树。
使用并查集 https://uoj.ac/submission/482165
或者单调栈也可以。

Posted by xiaodao
Category: 日常