本题数据急需加强
查看原帖
本题数据急需加强
82284
Echidna楼主2021/7/25 09:33

打开了题解区一看,然后发现 6060% 的题解由以下几种类型构成:

  1. 暴力 find(时间复杂度 O((i=1nleni)2)O((\sum\limits_{i=1}^nlen_i)^2),现在已经过不去了,但是在题解区,这样的错误算法仍然存在)

  2. 暴力 KMP 算法(时间复杂度 O(ni=1nleni)O(n\sum\limits_{i=1}^nlen_i)

  3. 不加树上差分的 AC自动机 。(最坏情况下时间复杂度 O(i=1nlenimaxi=1nleni)O(\sum\limits_{i=1}^nlen_i \max\limits_{i=1}^nlen_i)

对比一下正解的 O(i=1nleni)O(\sum\limits_{i=1}^nlen_i) ,我们会得出一个结论:这题的数据急需加强。

2021/7/25 09:33
加载中...