后缀数组

##简要


后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色,而且它比后缀树所占用的内存空间小很多。可以说,在信息学竞赛中后缀数组比后缀树要更为实用。本文分两部分。第一部分介绍两种构造后缀数组的方法,重点介绍如何用简洁高效的代码实现,并对两种算法进行了比较。第二部分介绍后缀数组在各种类型题目中的具体应用

##一些定义


(1) 子串:字符串 S 的子串 r[i..j],i≤j,表示 r 串中从 i 到 j 这一段,也就是顺次排列 r[i],r[i+1],…,r[j]形成的字符串。
(2)后缀:后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的 从 第 i 个 字 符 开 始 的 后 缀 表 示 为 Suffix(i) , 也 就 是Suffix(i)=r[i..len(r)]。
(3)大小比较:关于字符串的大小比较,是指通常所说的“字典顺序”比较,也就是对于两个字符串u、v,令i从1开始顺次比较u[i]和[i],如果u[i]=v[i]则令 i 加 1,否则若 $u[i]<v[i]$则认为 $<v,u[i]>v[i]$认为 u>v
(也就是 $vlen(u)或者 i>len(v)仍比较不出结果,那么 若 $ len(u)<len(v) $ 则 认 为 $ u<v$ , 若 len(u)=len(v) 则 认 为 u=v , 若len(u)>len(v)则 u>v。
从字符串的大小比较的定义来看,S 的两个开头位置不同的后缀 u 和 v 进行比较的结果不可能是相等,因为 u=v 的必要条件 len(u)=len(v)在这里不可能满足。
(4)后缀数组: 后缀数组 SA 是一个一维数组,它保存 1..n 的某个排列 SA[1] ,
SA[2],……,SA[n],并且保证 Suffix(SA[i]) < Suffix(SA[i+1]),$1≤i<n$ 。也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入 SA 中。
(5)名次数组:名次数组 Rank[i]保存的是 Suffix(i)在所有后缀中从小到大排列的“名次 ” 。


简单的说,后缀数组是“排第几的是谁? ” ,名次数组是“你排第几? ” 。 容易看出,后缀数组和名次数组为互逆运算。如图 所示。
这里写图片描述

设字符串的长度为 n。为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小。在求出名次数组后,可以仅用 O(1)的时间比较任意两个后缀的大小。在求出后缀数组或名次数组中的其中一个以后,便可以用 O(n)的时间求出另外一个。任意两个后缀如果直接比较大小,最多需要比较字符 n 次,也就是说最迟在比较第 n 个字符时一定能分出“胜负 ”。


#注


SA[] :第几名是谁
后缀数组:后缀数组 SA 是一个一维数组, 它保存 1..n 的某个排列 SA[1] ,SA[2],……,SA[n],并且保证 Suffix(SA[i]) < Suffix(SA[i+1]),$1≤i<n$ 。也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入 SA 中。
Rank[] 谁是第几名名次数组:名次数组 Rank[i]保存的是 Suffix(i)在所有后缀中从小到大排列的“名次 ” 。
r[]:原始数据j当前字符串的长度,每次循环根据2个j长度的字符串的排名求得2j长度字符串的排名.
y[]:指示长度为2j的字符串的第二关键字的排序结果,通过存储2j长字符串的第一关键字的下标进行指示.
wv[]:2j长字符串的第一关键字的排名序号.
ws[]:计数数组,计数排序用到.
x[]:一开始是原始数据r的拷贝(其实也表示长度为1的字符串的排名),之后表示2j长度字符串的排名.
p:不同排名的个数.
Heigth[i] : 表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀


##基数排序


1.对长度为1的字符串进行排序

1
2
3
4
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;

①用的是基数排序,也可以使用其它的排序
②r[]存储原本输入的字符串,x[]是对r[]的ASCII呈现(便于排序)
③m是一个估计数字,代表ASCII最大值,在循环中做边界
④n在这里是字符串的长度+1,后面的加加减减有所体现(貌似不介意直接用字符串的长度)
⑤最后一行比较难懂,但实践证明它确实是正确的,sa[i]=j表示第i名是j。
ws[i]是对第i及之前字符出现次数的累加,越往后ws[i]越大,而且对应的字符数值越大,举个例子,如果某一字符串为aaabaa,则a出现的次数为5,b出现的次数为1,按上述原理,可以看做ws[a]=5,ws[b]=6,固然a都在前5名,b在第六名。


2.进行若干次基数排序
因为前面排序的名次可能有重复,所以要再进行若干次,直到所有的名次都不再相同

1
2
3
4
5
6
7
8
9
10
11
12
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]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}

相对于上面函数的第一步来说,这一坨代码更加复杂了
①从最外层循环可以看出,j是处于倍增状态的,代表正在比较的每一小段字符串的长度
②循环内的第一行,循环了j-1次,是对后面几个数的提前处理(其第二关键字都为0)
如图
这里写图片描述

即所有加0的数
③第二行,再翻上去看一眼sa的作用。首先要明白这一行抛弃了一些东西,
这里写图片描述

由于是对第二关键字的排序,第一关键字先不看,所以有一条件if(sa[i]>=j)
这条语句后面y[p++]=sa[i]-j,要减去j也是因为这个
到这里,第二关键字的排序就完成了

④开始第一关键字的排序
假设需要排序的数为92 71 10 80 63 90
那么y[]=3 4 6 2 1 5 即对第二关键字排序后名次递增所对应的序号
x[]=10 80 90 71 92 63 即对第二关键字排序的结果
$for(i=0; i<n; i++) wv[i]=x[y[i]];$
将x[]数组拷贝到wv[]中
⑤剩下的基数排序就与对长度为1的字符串进行排序一样了