社区讨论

对此题AC自动机时间复杂度正确性的疑问

P14363[CSP-S 2025] 谐音替换参与者 4已保存回复 8

讨论操作

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

当前回复
8 条
当前快照
1 份
快照标识符
@mhz4jps2
此快照首次捕获于
2025/11/15 01:21
3 个月前
此快照最后确认于
2025/11/16 14:03
3 个月前
查看原帖
蒟蒻刚学ACAM,参照第一篇题解(可能理解有误),是对每一个问题都要做一次多模匹配,时间复杂度为O(L+Z)O(L+Z),LL为此问题的长度,ZZ为匹配成功的个数,但显然可以构造数据,让每个ZZ都达到qq级别,时间复杂度不就退化为nqnq了吗?或者说AC自动机不是一个一个的统计答案的吗,那ans\sum ans很显然可以构造出nqnq级别的.或者说我对题解做法的理解有误?

回复

8 条回复,欢迎继续交流。

正在加载回复...