半在线卷积的O(nlog^2/loglogn)算法
膜拜 $gg & EI & cy
膜拜 $gg & EI & cy
早就有迁移到动态博客的想法,不过太鸽了
由于我用的是Arch Linux
,一次滚动把nodejs滚到v14,然后hexo就坏了...
想了想不如干脆迁移到typecho,反正我也有国内主机。
文章大概都迁移过来了/cy
不过你想访问原来版本可以走https://old.qaq-am.com/
题意:有一个包含O,H,C的串,你现在只知道长度,每次可以询问一个串t在这个串里的所有出现位置,代价是$\frac{1}{|t|^2}$,你需要用不超过1.4的代价询问出这个串。
原发布于2020-01-14。
upd 2020-04-10: 代码写错了,被hack了,已更正
网上大多数都是$O(n\log^2 n)$的,不过我做法是$O(n\log n)$的...