08月11日漏签0天

noip吧关注：25,172贴子：642,067

26回复贴，共1页

<<返回noip吧

关于回文树时间复杂度

看到一个O(n)的证明，里面讲无论后缀链多长，每个点只会访问一次。
求大神讲讲为什么？

楼主太神啦！

不感兴趣

开通SVIP免广告

人工置顶
求大神求大神

因为Manichar(我一定拼错了)是O(n)的，所以回文树是O(n)的

水水水水水水水水水水水水水水水水水水

好像是nlog26还是好多。。如果字符集是常数时间就是线性的

这个不太了解

不感兴趣

开通SVIP免广告

因为和KMP类似。显然是O(n|∑|)的，计算空间复杂度就知道了。

应该是和sam一样分析的吧

同问顺便问问回文自动机是不也是这样

翁文涛论文上有讲... 势能分析就好辣.

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

26回复贴，共1页

<<返回noip吧

分享到: