本题数据急需加强
查看原帖
本题数据急需加强
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(n∑i=1nleni)O(n\sum\limits_{i=1}^nlen_i))

  3. 不加树上差分的 AC自动机 。(最坏情况下时间复杂度 O(∑i=1nlenimax⁡i=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
加载中...