avatar

后缀数组

关于后缀数组的一些说明

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

遇事不决上代码

请先欣赏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]);
}

开始前的准备

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

  1. sa[i] = j, 表示第i名的后缀是从j开始的,这里需要注意的是j是下标,不是字符。
  2. rk[i] = j, 表示从i下标开始的后缀的排名是j,这里可以注意到是和sa数组互逆的。
  3. tp[i] = j, 表示第二关键字排名为i的后缀是从j开始的,同样储存的是下标。
  4. tax[i] = j, 表示第一关键字排名为i的数,有j个
    下面就是具体的后缀排序的流程:
    Created with Raphaël 2.2.0开始把每个字母排序得到第一次的 sa 值根据上一次的 sa 值得到第二关键字按现在关键字排序得到新的 sa 值根据现在的 sa 得到新的第一关键字排名各不相同?结束yesno

代码分析

建在就是可以进行代码分析的时候了。
首先说的是代码中的一个优化,在一般的过程中可能有人认为吧关键字放到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];
}

最熟悉的图他来了

倍增的图就不用我多说了

未完待续

Author: icimence
Link: https://icimence.cn/2020/03/21/后缀数组/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
    微信
  • 支付宝
    支付宝

Comment