后缀数组SA笔记-爱代码爱编程
后缀数组是什么
后缀数组,SA,可用于解决字符串问题。
那我们看后缀数组:
先约束一些东西:
1.字符数组下标从1开始。
2.len表示字符数组的长度。
后缀数组主要有两个数组组成
s a [ i ] sa[i] sa[i] 表示字典序第 i i i小的后缀的开头下标 ( 1 − l e n ) (1-len) (1−len)
r k [ i ] rk[i] rk[i] 表示以下标为 i i i开头的后缀的字典序排名
那么显然有以下性质:
s a [ r k [ i ] ] = r k [ s a [ i ] ] = i sa[rk[i]]=rk[sa[i]]=i sa[rk[i]]=rk[sa[i]]=i
偷个图,以下即为
a
a
b
a
a
a
a
b
aabaaaab
aabaaaab的后缀数组
如何求后缀数组?
这里的方法是 O ( l e n ∗ l o g 2 l e n ) O(len *log^2len) O(len∗log2len) 的
看到2个 l o g log log,是不是有想法。
很显然其中一个是交给快排的 l o g log log,那么显然另外一个就是我们算法的核心了。
那么这个 l o g log log我们就放在倍增身上吧。
作为算法的核心,我们想一下这个算法倍增的思路:
我们先考虑一下子任务:长度为1的子串的字典序排序,相当好求吧?就一个快排就出来了。
那我们用递推的思想依次完成每个子任务
1
—
>
1
+
2
0
—
>
1
+
2
1
—
>
1
+
2
2
—
>
1
+
2
3
…
…
1—>1+2^0—>1+2^1—>1+2^2—>1+2^3……
1—>1+20—>1+21—>1+22—>1+23……
然后我们可以完成每个长度为
l
e
n
len
len的子串的字典序排序了
具体怎么实现呢?
我们每次对sa数组排序时取两个关键字 r k [ j ] 与 r k [ j + 2 i ] rk[j]与rk[j+2^i] rk[j]与rk[j+2i]
( i 为 当 前 枚 举 的 次 幂 , j 为 排 序 的 下 标 ) (i为当前枚举的次幂,j为排序的下标) (i为当前枚举的次幂,j为排序的下标)
然后我们再利用 s a sa sa数组来更新 r k rk rk数组
偷图帮助理解:
有图片理解应该相当轻松了吧!
CODE
码风奇怪,将就将就
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#include<bitset>
#include<queue>
#define ll long long
#define R register
#define I inline
#define N 1000005
#define mo
#define F freopen(".in","r",stdin),freopen(".out","w",stdout);
using namespace std;
int rk[N],sa[N],ork[N],len,u,now; char s[N];
I bool cmp(int x,int y) {return rk[x]==rk[y]?rk[x+u]<rk[y+u]:rk[x]<rk[y];}
I void print(int Lz) {Lz<0?putchar('-'),Lz=-Lz:Lz=Lz; if (Lz>9) print(Lz/10); putchar(Lz%10+'0');}
int main() {
scanf("%s",s+1),len=strlen(s+1);
for (R int i=1;i<=len;i++) sa[i]=i,rk[i]=s[i];
for (R int i=1;i<len;i*=2) {
u=i,sort(sa+1,sa+1+len,cmp);
for (R int j=1;j<=len;j++) ork[j]=rk[j]; rk[sa[1]]=now=1;
for (R int j=2;j<=len;j++) rk[sa[j]]=(ork[sa[j]]==ork[sa[j-1]]&&ork[sa[j]+u]==ork[sa[j-1]+u])?now:++now;
} for (int i=1;i<=len;i++) print(sa[i]),putchar(' ');
}
解释以下 o r k ork ork的部分:
因为 r k rk rk数组是实时更新的,所以在更新之前我们要记录一下原数组,作为我们的比较依据。