社区讨论

蒟蒻弱弱的问一句时间复杂度

2018/11/06 19:00P3796AC 自动机（简单版 II）参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

这道题，大部分题解采用的都是暴力跳fail（或者优化过的，记录last的跳fail），但是本质上还是，一个点会被fail经过好几遍啊，如何保证复杂度呢？

简单版也有相同的疑问；

~~所以本蒟蒻建了棵fail树，然后用树状数组求子树和，起码复杂度有了保证 $O(len \log len)$ ，但是跑的比暴力跳fail的做法慢1倍~~

为什么呢？

共 4 条回复，欢迎继续交流。

正在加载回复...