后缀数组（SA）学习笔记

Demeanor_Roy · 2023-05-09 21:45:08 · 个人记录

• 像这种抽象算法还是记录一下吧。

符号约定

算法作用：

• 求出 sa 数组和 height 数组。

• 借用 height 数组求任意两个后缀的最长公共前缀。

具体流程

SA 算法分为两部分。分别是求解 sa 与 height 数组。

第一部分以倍增为基本思想：

假设我们已经求出了只考虑每个后缀前 k 个字符的字典序排名，我们可以通过此信息求出所有后缀只考虑前 2k 个字符的字典序排名。以此类推，我们就可以在最多 \log n 次倍增的过程中，求出 sa 数组。

现在我们来看每一次倍增具体如何实现。既然每一个后缀要考虑前 2k 个字符，我们可以先考虑前 k 个字符再考虑后 k 个字符，不难发现前者所决定的顺序已知，后者亦可以用上一次信息推出。具体来说，我们先将长度不超过 k 的后缀放置在最前面，然后遍历从小到大上一次 sa 数组，显然若 sa_i > k，那么 sa_i - k 即为当前按第二关键字排序最小。

而得到按两个关键字分别排序的数组后，我们只需用基数排序进行一次双关键字排序即可完成流程。值得注意的是，我们在每次倍增后，需将前 k 个字符按字典序离散化来确保基数排序的进行。

这部分代码如下：

inline void SA()
{
    for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1)
    {
        int num=0;
        for(int i=n-k+1;i<=n;i++) y[++num]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
        for(int i=1;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        num=x[sa[1]]=1;
        for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        if(num==n)  break;m=num;
    }
}

第二部分则需要一个结论。

• 断言：height[rk_i] \geq height[rk_{i-1}] - 1。

此结论易证，此处不详细说明。有了此结论后，我们只需从前往后求解 height[rk_i]，由于求解时答案指针最多减少 n，并且最多增至 n，故可做到线性求解 height 数组。

再考虑如何用 height 数组求解任意两个后缀的最长公共前缀，有结论：

二者关系大于等于显然，小于等于可以用夹逼法证明。于是我们维护