后缀数组简介

[Enter-tainer]

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

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[widsnoy]

将 rk[id[i]] 存下来，减少不连续内存访问

感觉这个优化是没有必要的，比如我可以把原文的代码改成这样

    //for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
    for (i = 1; i <= n; ++i) ++cnt[rk[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    //for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
    for (i = 1; i <= n; ++i) sa[cnt[rk[id[i]]]--] = id[i];;

[liangruichen]

$p = n$ 时直接 break 就行了吧。。。

[hly1204]

确实是这样，其实我在当时加这个 early break 的时候看到了 OI-wiki/OI-wiki#3054 。。不过后来没有思考为什么

[Singulet31258]

Milk Patterns这道题不是SAM裸题吗？在SAM的后缀链接树上DP维护出现次数，然后遍历整颗树找出len最大的出现次数>=k的结点即可。用SA做还麻烦一些，还要单调队列或者二分哈希什么的。

[Day719]

写得真好！！！

[AKNOIXZQ]

为什么 $height[i]$ 的定义是 $lcp(sa[i],sa[i-1])$ 不应该是 $lcp(suf[i],suf[i-1])$ 吗， $suf[i]$ 表示第 $i$ 名的后缀， $sa[i]$ 不应该是排完序第 $i$ 名在原字符串中的编号吗，有没有 dalao 讲讲/kk

[AKNOIXZQ]

蒟蒻第一天学 SA，说错了请见谅

[Nanarikom]

「下文中以 lcp(i,j) 表示后缀 i 和后缀 j 的最长公共前缀（的长度）。」

[AKNOIXZQ]

哦，懂了懂了，也就是 $lcp(i,j)$ 中的 $i,j$ 是编号，滞涨了

[auto-iterator]

求SA那可以把 memcpy 换成交换指针，还能再卡个常

[lnw143]

$height$ 数组中

所以 $AB \leqslant$ 后缀 $sa[rk[i]-1] < AD$，显然后缀 $i$ 和后缀 $sa[rk[i]-1]$ 有公共前缀 $A$。

为什么 $sa[rk[i]-1]$ 不能等于 $AD$ ？

[lnw143]

对不起，本人初学 SA 有点不理解，现在懂了

[JYRowe]

那么问题来了，在 2004 国集论文中写 SA 的那位 dalao 不是姓许嘛

[JYRowe]

请问 这一子目 是不是可以通过二分 $\text{LCP}$ 的将时间复杂度进一步降到 $\mathcal{O}(\log|S|\log|T|)$？

[Mr-Python-in-China]

“用函数 cmp 来计算是否重复”的常数优化有点太抽象了吧 想不出任何道理能变快

实测也只能得到评测机波动的结论

早就是O2时代了 这点小聪明没什么必要 建议删除

[Floze3]

请问一下，如果后缀排序按照给定的写法，if (rk[i] == 0) continue; 是否应改为 if (rk[i] == 1) continue;？

[zja601]

关于height数组，无论排名还是编号，示例代码又是从0开始了，与此节开头部分约定的从1开始矛盾了。