Jumbo的博客

博客

2018-12-27 20:23:04 By Jumbo

bzoj 3473 的其中一个解法是建出广义后缀自动机然后每个点暴力向上跳parent并不断加size，跳到已经加过为止

这样的话复杂度从感觉上是线性的，但是15年队爷张天扬《后缀自动机及其应用》中提到这种方式的复杂度为$O(n\sqrt n)$，但是本蒟蒻不知道为什么，所以跪求一位好心的大哥帮忙解答一下

_mangoyang

![见此](https://www.cnblogs.com/mangoyang/p/10155185.html)

mangoyang

？？？？？？谁在仿我的id =w=

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。