Open CTP314 opened 5 years ago
https://ctp314.github.io/2019/07/02/%E9%9B%85%E7%A4%BC%E9%9B%86%E8%AE%AD2017Day7-%E4%BA%8B%E6%83%85%E7%9A%84%E7%9B%B8%E4%BC%BC%E5%BA%A6/#more
P6041 [雅礼集训2017Day7]事情的相似度 给定前缀结束位置区间，求其两两间 $LCS$ 的最大值 一个人学 $SAM$，也需要考虑历史的进程 这道题在一开始有一个口胡的后缀数组和莫队的 $O(n\sqrt{nlogn})$ 做法，但觉得常数有点大，就放弃了 之后又错误估计了预处理的点对数量，以为是 $O(n^2)$，然后就看了题解，发现是 $O(nlogn)$ 任意两前缀的 $LCS
OrzOrz
WA-automaton
commented
5 years ago WA-automaton
commented
5 years ago
https://ctp314.github.io/2019/07/02/%E9%9B%85%E7%A4%BC%E9%9B%86%E8%AE%AD2017Day7-%E4%BA%8B%E6%83%85%E7%9A%84%E7%9B%B8%E4%BC%BC%E5%BA%A6/#more
P6041 [雅礼集训2017Day7]事情的相似度 给定前缀结束位置区间，求其两两间 $LCS$ 的最大值 一个人学 $SAM$，也需要考虑历史的进程 这道题在一开始有一个口胡的后缀数组和莫队的 $O(n\sqrt{nlogn})$ 做法，但觉得常数有点大，就放弃了 之后又错误估计了预处理的点对数量，以为是 $O(n^2)$，然后就看了题解，发现是 $O(nlogn)$ 任意两前缀的 $LCS