后缀数组学习路径以及后缀数组板子推送_算法日常[15/100]

发表于 更新于 分类于 阅读次数：
后缀数组学习路径以及后缀数组板子推送_算法日常

学习后缀数组的小建议

时刻分析数组含义

学习后缀数组的核心是时刻分析这到底是排名i的后缀位置还是后缀i的排名值

一般的SA[i]代表着排名第i的后缀位置从哪里开始

然后Rank[i]代表着后缀i的排名

后缀i就从下标i开始一直到字符串末尾的那个后缀s.substr(i)

演算

脑子的内存是有限的，所以有时候想不出来，尽量使用草稿纸加以演算，这样才能更高效地学习后缀数组(否则像小编这种脑子不怎么好使的，不演算之前看了一天都没看懂某两行代码)

后缀数组学习材料

当然小编也是一个初学者，所以暂时只能说出一些学习的小建议，让我写出来还是不太现实，不过小编可以给你们推荐一些学习的资料

论文

下面这篇论文基本上网罗了后缀数组的方方面面，而且写得也十分详细，所以十分推荐
后缀数组论文分享

学习网址

也挺详细的

OI-wiki上的介绍

题目链接

当然是先刷一手kuangbin专题

板子整理推送(LTS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
板子声明 :
1. r从0开始,而非像oi-wiki中的从1开始
2. [build使用 n + 1 , calheight 使用 n ](https://www.wolfdan.cn/2019/08/21/%E7%AE%97%E6%B3%95%E6%97%A5%E5%B8%B8-16-100/)

*/
int sa[maxn],wa[maxn],wb[maxn],wv[maxn],ws[maxn];
/*LCP:最长公共字串部分*/
int rank[maxn],height[maxn];

/*r为字符串数组,sa是后缀数组,n为字符串长度,m为字符种类数*/
void da(int *r,int *sa,int n,int m){
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) ws[i]=0;
    for(i=0;i<n;i++) ws[x[i]=r[i]]++;
    for(i=1;i<m;i++) ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;

    for(j=1,p=1;p<n;j*=2,m=p){
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        /*提取第一关键字*/
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        for(i=0;i<m;i++) ws[i]=0;
        for(i=0;i<n;i++) ws[wv[i]]++;
        for(i=1;i<m;i++) ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
        x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&r[sa[i-1]+j]==r[sa[i]+j])?p-1:p++;
    }
    return;
}

/*r为字符串数组,sa是后缀数组,n为字符串长度*/
void calheight(int *r,int *sa,int n){
    int i,j,k=0;
    /*用sa[]得到rank[]*/
    for(i=1;i<=n;i++) rank[sa[i]]=i;
    /*j就是后缀i的前一名的后缀位置,然后如果前一个串之间有k,那么就从k--起步*/
    for(i=0;i<n;height[rank[i++]]=k)
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
    return;
}

每天一句叨叨

愿回首岁月之时，你不会后悔