over 2 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3926
分析:
传说中的多串后缀自动机。。。今天膜了一发
由于叶子结点数很少,我们可以倒过来从每个叶子结点建一棵树,然后合并成一个大树(实际上可以直接合并)。
接着就是询问树上的子串个数,注意树上的子串都是从深度小的到深度大的。
这个怎么做呢,就是处理出序,按序从一个结点的父节点扩展即可。
然后要么就是统计集合,要么直接一遍也可以,要用哦。
bzoj3926.cpp

← bzoj1041:[HAOI2008]圆上的整点 bzoj1042:[HAOI2008]硬币购物 →
 
comments powered by Disqus