BZOJ 1396 识别子串


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1396

题意:见原题面。


建立 SAM,显然只有那些 right 集合大小为 1 的状态可以更新答案。

怎么更新答案的呢? 令 R 为这个状态代表的串的右端点,则 R 到 R-min 这段可以直接用 min 这个长度。

对于 R-min 到 R-max 这段,可以用 max-i 这个等差数列的长度去覆盖,分别维护两颗线段树即可。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1396 识别子串


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,