学习后缀数组的小建议
时刻分析数组含义
学习后缀数组的核心是时刻分析这到底是排名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;
}
|
每天一句叨叨
愿回首岁月之时，你不会后悔