后缀数组 | icimence's Tech Blog

关于后缀数组的一些说明

本文撰写的目的在于做题时发现经常会有题目出现后缀数组的解法，而普通的暴力解法容易引起超时，所以特意在网上学了后缀数组，但是感觉网站的一些版本都不是特别清晰，所以在自己的博客中打算自己写一个份算法教程。

遇事不决上代码

请先欣赏Cpp的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAX=1e6+5;
int n,m;
int tax[MAX],rak[MAX],tp[MAX],sa[MAX];
char s[MAX];

void sort(int a[],int b[]){
    for(int i=0;i<=m;i++)tax[i]=0;
    for(int i=1;i<=n;i++)tax[a[i]]++;
    for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
    for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i];
}

bool comp(int r[],int a,int b,int k){
    return r[a]==r[b]&&r[a+k]==r[b+k];
}

void get_sa(int a[],int b[]){
    for(int i=1;i<=n;i++)
    m=max(m,a[i]=s[i]-'0'),b[i]=i;
    sort(a,b);
    for(int p=0,j=1;p<n;j<<=1,m=p){
        p=0;
        for(int i=1;i<=j;i++)b[++p]=n-j+i;
        for(int i=1;i<=n;i++)if(sa[i]>j)b[++p]=sa[i]-j;
        sort(a,b);
        int *t=a;a=b;b=t;
        a[sa[1]]=p=1;
        for(int i=2;i<=n;i++)
        a[sa[i]]=comp(b,sa[i],sa[i-1],j)?p:++p;
    }
}

int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    get_sa(rak,tp);
    for(int i=1;i<=n;i++)printf("%d ",sa[i]);
}

开始前的准备

在这里先进行一些后缀数组中的说明：首先让我们看一看这个程序中要用到的诸多参数，都是令人迷惑的东西。

sa[i] = j，表示第i名的后缀是从j开始的，这里需要注意的是j是下标，不是字符。
rk[i] = j，表示从i下标开始的后缀的排名是j，这里可以注意到是和sa数组互逆的。
tp[i] = j，表示第二关键字排名为i的后缀是从j开始的，同样储存的是下标。
tax[i] = j，表示第一关键字排名为i的数，有j个
下面就是具体的后缀排序的流程：

代码分析

建在就是可以进行代码分析的时候了。
首先说的是代码中的一个优化，在一般的过程中可能有人认为吧关键字放到pair中进行一次sort就可以解决，但是这里要介绍一种基数排序。

具体的代码如下；

void sort(int a[],int b[]){
    for(int i=0;i<=m;i++)tax[i]=0;
    for(int i=1;i<=n;i++)tax[a[i]]++;
    for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
    for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i];
}