后缀数组学习笔记

前置

纯属博主虎的的
罗穗骞2009NOI集训队论文
还是原版的最明白啊
先了解基数排序和倍增求sa思想
并且有一定的看别人博客的基础(对，没错，就是这么不要脸)
基数排序=>博客
这里主要说一下代码的理解及重要点

重点及其目标

根据后缀子串，他们一定是两两不同的
rk和sa也是差不多反函数关系，那rk也是不重复的
所以我们最终的目标是求出rk中无重复时的sa数组，根据定义-最差倍增到n
总的来说，求sa的过程就是不断地用基数排序倍增直到rk无重复
而基数排序从代码中很容易看出
就是是用rk[]和x[]求出sa[]的过程(封装)
那如何用rk[]和x[]求出sa[]就成了重中之重
如果明白了这个就基本理解倍增求sa的过程了

分析目标&&正题

ps:这里基数排序按照从低到高排序
我们一共有俩关键字

FOR(i,n-k+1,n) x[++num]=i;
FOR(i,1,n) if (sa[i]>k) x[++num]=sa[i]-k;

这是弄出第二关键字排序的x[]的过程
利用了上次和这次之间的交错关系
然后有的地方第二关键字没有，也就是-INF，要放在前面，还是老话，画图去
求出第二关键字排完序的x[]
这就说明我们已经完成了基数排序的一半任务了
剩下的就是利用第一关键字来排序了

FOR(i,1,n) ++c[rk[i]];
FOR(i,2,m) c[i]+=c[i-1]; 
ROF(i,n,1) sa[c[rk[i]]--]=i; 

c[rk[x[i]]]-- 下标
x[i] 权值
这是根据for循环来臆测的
x[i]这是按照第二关键字排序的顺序来进行的，我们可以把x[i]看做j
也就是
c[rk[j]]-- 下标
j 权值
注意到，上下两层的第一关键字是不变的,那第一关键字就好弄了
我们用上一次的sa捣鼓出来，存在rank里面
所以就是sa[rk[j]]=j喽，但是,rk是会有重复的呀
而且我们还不知道c[]的作用呢
其实c[]就是统计个数来确定的sa的次序的
这样倍增范围是不断增大，那么重复数也会慢慢变少，直到无重复(定义)

然后后面就是一堆处理来保证下一次操作的正常运行以及判断结束
还算好理解，嗯

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int maxn=1000050;
char s[maxn];
int n,m,x[maxn],rk[maxn],c[maxn],sa[maxn];
void get_SA()
{
    FOR(i,1,n) ++c[rk[i]=s[i]];
    //rk[i]是第i个元素的第一关键字 
    FOR(i,2,m) c[i]+=c[i-1]; 
    //做c的前缀和，我们就可以得出每个关键字最多是在第几名 
    ROF(i,n,1) sa[c[rk[i]]--]=i; 
    for(int k=1;k<=n;k<<=1) {
        int num=0;
        //@按照第二关键字进行排序
        FOR(i,n-k+1,n) x[++num]=i;
        FOR(i,1,n) if (sa[i]>k) x[++num]=sa[i]-k;
        FOR(i,1,m) c[i]=0;
        FOR(i,1,n) ++c[rk[i]];
        FOR(i,2,m) c[i]+=c[i-1];
        //@依次取出x[i]，按照第一关键字排序
        ROF(i,n,1) sa[c[rk[x[i]]]--]=x[i],x[i]=0;
        //@这里不用想太多，因为要生成新的rt时要用到旧的，就把旧的复制下来，没别的意思 
        swap(x,rk);
        //@制造新的rk
        rk[sa[1]]=1;num=1;
        FOR(i,2,n)
            rk[sa[i]]=(x[sa[i]]==x[sa[i-1]] && x[sa[i]+k]==x[sa[i-1]+k]) ? num : ++num;
        //判断
        if (num==n) break;
        m=num;
    }
    FOR(i,1,n) cout<<sa[i]<<" ";
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1),m=122;
    get_SA();
    return 0;
}