BZOJ 1396 识别子串

发布于 2018-03-15  116 次阅读


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

题意:见原题面。


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

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

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

 


一个非常弱的准退役OIER