后缀数组代码浅析

mwz3 · 2025-04-29 22:03:31 · 算法·理论

本文只是对后缀数组代码的分析，并无对思路的讲解，建议没有基础的同学不要阅读本文。

变量定义：

• 1. 类似于映射，用来存放「**第二关键字排名为** $i$」的第一关键字的位置。 2. 在求新的 $rk$ 数组时记录老的 $rk$ 数组。

综述

• 为么不能直接用 sa[rk[i]]=i 来推导呢？因为 sa_i 不可重复，而 rk_i 可以重复。

Part 1 求出初始的 sa_i

for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];

• 由于 rk_i 可以重复，每个后缀的初始排名就是 s_i。

• 重复一遍，cnt_i 记录的是「排名小于等于 i 的后缀」有多少个。

for(int i=1;i<=n;i++)sa[cnt[rk[i]]--]=i;

• 难点：为什么此处要用 cnt_{rk_i}？

  答：「以 i 位置开头的后缀」所对应的桶就是 cnt_{rk_i}。

  首先，「以 i 位置开头的后缀」对应的排名是 rk_i（rk_i 可以重复）；其次，因为 cnt_i 存放的是排名，所以我们直接访问 cnt_{rk_i} 即可。

• 有些代码在这里写的是逆序循环，但正序循环也可以，关键还是在于这里没有第二关键字。

Part 2 通过 rk_i 求 sa_i

int now=0;
for(int i=n-k+1;i<=n;i++)ls[++now]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)ls[++now]=sa[i]-k;

• 重复一遍，ls_i 类似于映射，用来存放「第二关键字排名为 i」的第一关键字的位置。

• 首先，「第一关键字开头在 [n-k+1,n] 之间的」没有第二关键字，因为我们要按照第二关键字有序，所以把这些第一关键字放到最前面。

• 然后我们从 1 到 n 循环，注意此时 i 代表的是第二关键字的开头位置。如果 sa_i>k，即这个第二关键字有第一关键字，就把它加入 ls 数组中。

  那么我们怎么保证 ls 有序呢？注意到我们的 sa 数组是有序的（「排在第 i 名的后缀」的开头位置），所以 ls 也是有序的。

for(int i=1;i<=m;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[rk[i]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];

• 注意此处桶储存的是第一关键字。

• 有的代码第二行是 cnt[rk[ls[i]]]++，可以用以下两种方式来理解：

for(int i=n;i>=1;i--)sa[cnt[rk[ls[i]]]--]=ls[i];

• 注意此处必须要逆序循环，原因是有第二关键字。

• 桶已经帮我们确定好了第一关键字，我们需要排序的是第二关键字。第二关键字由谁来呢？我们刚刚求得的 ls 正好可以用上了！

• 桶中可能有重复的数字，因为桶是拿出一个排名就减一，所以我们需要保证第二关键字逆序取出。

• 所以说桶的作用到底是什么？化重复为不重复。这也正好对应了 rk_i 的可以重复和 sa_i 的不可重复。

Part 3 由 sa_i 求出 rk_i

swap(ls,rk);m=0;
for(int i=1;i<=n;i++)rk[sa[i]]=(ls[sa[i]]==ls[sa[i-1]]&&ls[sa[i]+k]==ls[sa[i-1]+k])?m:++m;
if(m==n) break;

• 这一段就较为简单了，由于 sa 是已经排序完成的，我们只用比较两个关键字是否完全相同，若完全相同则 rk 就不用 +1。这也正好对应了 sa 数组的不可重复和 rk 数组的可以重复。

完整代码如下。

#include<bits/stdc++.h>
using namespace std;
int sa[1000001],rk[1000001],ls[1000001],cnt[1000001];
int main(){
//  freopen("P3809_2.in","r",stdin);
    string s;cin>>s;int n=s.size();s=" "+s;int m=128;
    for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
    for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++)sa[cnt[rk[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int now=0;
        for(int i=n-k+1;i<=n;i++)ls[++now]=i;
        for(int i=1;i<=n;i++)if(sa[i]>k)ls[++now]=sa[i]-k;
        for(int i=1;i<=m;i++)cnt[i]=0;
        for(int i=1;i<=n;i++)cnt[rk[i]]++;
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[rk[ls[i]]]--]=ls[i];
        swap(ls,rk);m=0;
        for(int i=1;i<=n;i++)rk[sa[i]]=(ls[sa[i]]==ls[sa[i-1]]&&ls[sa[i]+k]==ls[sa[i-1]+k])?m:++m;
        if(m==n) break;
    }
    for(int i=1;i<=n;i++)
        cout<<sa[i]<<" ";
    return 0;
}