很好奇为什么二分不等分就能过掉
by lcyxds @ 2021-03-10 09:33:17
@[lcyxds](/user/124314) 时限一秒你能过吗
by LeavingZ @ 2021-03-10 09:37:42
~~未曾设想的道路~~
by vectorwyx @ 2021-03-10 09:38:46
@[_Leaving](/user/215697) 过不了
~~所以没用~~
by lcyxds @ 2021-03-10 09:39:05
所以你把代码发出来干嘛
by LeavingZ @ 2021-03-10 09:39:31
这样做最坏复杂度是劣于 $O(n\log^2n)$ 的吧，数据可能是出水了所以被艹过去了（
by vectorwyx @ 2021-03-10 09:40:53
问题是我没懂为什么改变二分位置就能过（
普通二分是过不了的
by lcyxds @ 2021-03-10 09:42:05
你这个`1000000`个`a`难道不会飞吗
by w23c3c3 @ 2021-03-10 09:44:01
@[lcyxds](/user/124314) 因为把取中点改为了取距离左端点 $\frac{3}{8}(r-l)$ 的点，所以如果比较的两个字符串的 LCP 比较小的话这种方法会更快地收束到目标位置
by vectorwyx @ 2021-03-10 09:45:25
但是，如果 LCP 比较大的话这个方法就会变得很慢。比如说输入给你 1e6 个 a 就会 T 飞吧（
by vectorwyx @ 2021-03-10 09:46:59