后缀数组 (SA)

[Ir1d]

https://oi-wiki.org/string/sa/

[hehelego]

qwq之前那个最简单的暴力是不是O(N^2logN)的啊qwq...

[Ir1d]

@hehelego 是哎…… 欢迎pr

[wx40217]

要求解消耗额外空间复杂度的两子串最长公共前缀求解的时候应该把模板中的c数组怎样调整呃

[MikuOvO]

内个nlog^2n求后缀数组的代码好像有点问题，应该是w<<=1

[Prurite]

不是有线性的后缀排序吗

[CyaceQuious]

“结合线段树”有没有什么例题呀qaq

[EndlessCheng]

SA-IS 和 DC3 的性能对比：https://riteme.site/blog/2016-6-19/sais.html#5

[widsnoy]

快速排序求SA的做法如果把

return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];

改为

return rk[x] == rk[y] ? rk[x + w] <= rk[y + w] : rk[x] <= rk[y];

就会RE,为什么？

[ShuYuMo2003]

USACO06DEC Milk Patterns 这道题的代码 @ouuan 请问，ans = max(ans, *t.begin());，不是应该在if (i > k)的条件下更新呢？不是应该保证使用连续k - 1个数字的最小值更新答案吗QAQ？

[ouuan]

USACO06DEC Milk Patterns 这道题的代码 @ouuan 请问，ans = max(ans, *t.begin());，不是应该在if (i > k)的条件下更新呢？不是应该保证使用连续k - 1个数字的最小值更新答案吗QAQ？

这份代码中 height[1] 是 0，所以不影响正确性。但加上判断并且从 2 开始枚举会更好。（这份代码开头的 --k 也挺迷惑的..）

[ShuYuMo2003]

@ouuan

USACO06DEC Milk Patterns 这道题的代码 @ouuan 请问，ans = max(ans, *t.begin());，不是应该在if (i > k)的条件下更新呢？不是应该保证使用连续k - 1个数字的最小值更新答案吗QAQ？

这份代码中 height[1] 是 0，所以不影响正确性。但加上判断并且从 2 开始枚举会更好。（这份代码开头的 --k 也挺迷惑的..）

--k 应该是保证连续长度为k-1的区间更新答案，后面也许会好写（？）。但是所更新的答案并没有保证set中的元素数量等于k-1。（这份代码不是ouuan您写的嘛QAQ…（在你的博客里看到的QAQ QWQ））

[ouuan]

--k 应该是保证连续长度为k-1的区间更新答案，后面也许会好写（？）。但是所更新的答案并没有保证set中的元素数量等于k-1。（这份代码不是ouuan您写的嘛QAQ…（在你的博客里看到的QAQ QWQ））

我知道 --k 的作用，这份代码也是我写的，这和我觉得它迷惑不冲突。

现在我知道了你注意到了我括号里的一个小小吐槽，但我不清楚你是否明白了我前面对你的问题的回答：“这份代码中 height[1] 是 0，所以不影响正确性”。

[ShuYuMo2003]

我知道 --k 的作用，这份代码也是我写的，这和我觉得它迷惑不冲突。

现在我知道了你注意到了我括号里的一个小小吐槽，但我不清楚你是否明白了我前面对你的问题的回答：“这份代码中 height[1] 是 0，所以不影响正确性”。

Hi~ 但是height[1]=0并不能保证正确性啊QAQ，k 不一定仅仅是2呀？可能我理解错了，我再思考一下，谢谢你的时间。

[ShuYuMo2003]

@ouuan 我明白了，提前更新并不会影响正确性，即使答案位置<k，也一定能在后面满足区间长度=k的位置更新。 不好意思，我想错了。

[hkr04]

@widsnoy
快速排序求SA的做法如果把

return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];

改为

return rk[x] == rk[y] ? rk[x + w] <= rk[y + w] : rk[x] <= rk[y];

就会RE,为什么？

重载不等号的时候取等可能会使程序得到"a<b同时b<a"的判断而导致re，所以不能取等。同样的，在莫队算法中此类问题也较为常见。

[Clouder0]

height 数组应用中，比较一个字符串的两个子串大小关系，$A = S[a..b]$，$B = S[c..d]$，那么 $A &lt; B$ 是 $rk[a] &lt; rk[c]$ 还是原文中的 $rk[a] &lt; rk[b]$?

[ouuan]

height 数组应用中，比较一个字符串的两个子串大小关系，$A = S[a..b]$，$B = S[c..d]$，那么 $A &lt; B$ 是 $rk[a] &lt; rk[c]$ 还是原文中的 $rk[a] &lt; rk[b]$?

应该是 rk[a] < rk[c]，愿意开个 PR 来修正吗？

[fei0319]

还不如把倍增循环的条件改为 m<n 比那些扯淡的缓存优化不知快到哪里去