BZOJ 2555 SubString

发布于 2018-01-23  115 次阅读


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

题意:

给你一个字符串 init,要求你支持两个操作
    
    (1): 在当前字符串的后面插入一个字符串
    
    (2): 询问字符串 s 在当前字符串中出现了几次?(作为连续子串)
    
    你必须在线支持这些操作。


即在线询问 right 集合大小,即 fail 树中叶子节点个数。

lct 维护即可,有根树 lct 细节有点差别,不过会好写一点。

 


一个非常弱的准退役OIER