后缀数组
noco
2018-05-24 19:11:05
## 后缀数组代码及注释
```cpp
// 后缀数组
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+1e3+7;
int n;
int wa[N],wb[N],wv[N];
int sa[N],height[N],rank[N];
/* 后缀数组 SA 是一个一维数组， 它保存 1..n 的某个排列 SA[1] ，
SA[2]，……，SA[n]，并且保证 Suffix(SA[i]) < Suffix(SA[i+1])，1≤i<n 。
也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺
次放入 SA 中 SA从0开始记录
名次数组 Rank[i]保存的是 Suffix(i)在所有后缀中从小到大排列的“名次”。
height 定义 height[i]=suffix(sa[i-1])和 suffix(sa[i])的最长公
共前缀，也就是排名相邻的两个后缀的最长公共前缀*/
int tong[N];//桶容器 按字符种类建桶 排序使用
char s[N];
bool cmp(int *s,int a,int b,int l){
return s[a]==s[b]&&s[a+l]==s[b+l];
}// 通过二元组的两个下标的比较 来确定两个子串是否相同
void da(char *r,int *sa,int n,int m){
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++)
tong[i]=0; //清空
for(i=0;i<n;i++)
tong[x[i]=r[i]]++;
//不同字符新建一个桶 相同字符放进同一个桶中 并扩展大小 此处x相当于将母串复制一遍
for(i=1;i<m;i++)
tong[i]+=tong[i-1];
// 当前桶内字符的排名都维护一个前面所有点的前缀和
for(i=n-1;i>=0;i--)//倒着扫 可以|手动模拟 ！！|
sa[--tong[x[i]]]=i;
// 在满足第一关键字的同时 再满足第二关键字的要求
/*这里 x 数组保存的值相当于是 rank 值。下面的操作只是用 x 数组来比较字
符的大小，所以没有必要求出当前真实的 rank 值*/
for(j=1,p=1;p<n;j<<=1,m=p)//倍增法进行基数排序 j为当前字符串长度 p为当前字符集大小
{
/*基数排序要分两次，第一次是对第二关键字排序，第二次是对第一关键字排序。
对第二关键字排序的结果实际上可以利用上一次求得的 sa 直接算出,没有必要再算一次 */
// y[]的下标就是对应的第二关键字排名 y[]的内容就是第一关键字所在位置
for(i=n-j,p=0;i<n;i++)//因为是后缀排序 因此从n-j+1开始
y[p++]=i;
/*这一步就是在n-j+1到n这个范围内进行排序 根据基数排序的性质 长度不足j的子串一定排在前边
y记录在排到第p位时 其后缀排名*/
for(i=0;i<n;i++)
if(sa[i]>=j)//i这一位是否可以作为第二关键字
y[p++]=sa[i]-j;
/*这里的p起始时已为j 而对与排序来说 这里应减去j才可得到在原串中位置 */
// 第一次：第二关键字排序 y保存对第二关键字排序的结果
/*x[]的内容就是对应的第一关键字排名
根据x[]的内容和y[]的下标进行合并，得到新的排名作为sa[]的下标*/
for(i=0;i<m;i++)
tong[i]=0;//清空桶容器
for(i=0;i<n;i++)
tong[wv[i]=x[y[i]]]++;
/*x为对应的第一关键字的排名 类似于两位数的基数排序大小比较
在满足第一关键字的前提下 再满足第二关键字的条件
并在wv数组中复制此排名 以此排名作为桶的下标然后扩展容器大小*/
for(i=1;i<m;i++)
tong[i]+=tong[i-1];//当前桶的排名即维护前面所有桶大小的前缀和
for(i=n-1;i>=0;i--)//同样倒着扫
sa[--tong[wv[i]]]=y[i];
/*wv数组中也就得到了x的内容和y的下标进行合并后新的排名
并把这个排名和桶的大小排名一起作为sa的下标 并且根据y的下标为第二关键字排名
进行倒搜 因为桶是倒着退的 然后将sa的内容赋为y的内容 即第一关键字的位置
*/
//第二次：第一关键字排序
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++;
/*
1.可能有多个字符串的 rank 值是相同的，所以必须比较两个字符串是否完全相同
也就是cmp函数的作用 y 数组的值已经没有必要保存 为了节省空间 这里用 y 数组保存 rank值
这里又有一个小优化，将 x 和 y 定义为指针类型，复制整个数组的操作可以用交换指针的值代替
2.规定 r[n-1]=0 的好处：如果 r[a]=r[b] 说明以 r[a]或 r[b]开头的长度为l的字符串肯定不包括字符r[n-1]
所以调用变量 r[a+l]和r[b+l]不会导致数组下标越界，这样就不需要做特殊判断
3.p在这里储存的也就是不同字符串的大小
*/
//最后 求取rank数组 这里x的内容也就是rank值 下标为位置
//在第一次排序后 rank数组中最大值小于p 因此在循环起始时使m=p
}
}
//下一步进行对height数组的求解
/*设rank[j]<rank[k],则有以下性质：suffix(j)suffix(k)的最长公共前缀height[rank[j]+1],
, height[rank[j]+2], , height[rank[j]+3], … … ,height[rank[k]] 中的最小值。
原因：可以考虑如果一直向下推 相当于在相邻最长公共前缀前逐一添加限制 因此排名越靠后 限制越多
因此 在其中取最小值 即限制最多的最长公共前缀 */
void calheight(char *r,int *sa,int n){
int i,j,k=0;
//首先提取rank数组
for(i=1;i<=n;i++)
rank[sa[i]]=i;
/*根据上一步中所求出的sa的值来获取rank的值 用sa的内容即排好序后后缀的位置作为rank数组的下标
根据sa数组的性质rank数组的内容也就是i 因为已经排好序了啊*/
//然后计算height数组
/*定义 h[i]=height[rank[i]]，也就是 suffix(i)和在它前一名的后缀的最长公共前缀。
h数组有以下性质：h[i]≥h[i-1]-1
证明：设suffix(k)是排在 suffix(i-1)前一名的后缀，则它们的最长公共前缀是h[i-1]。
那么suffix(k+1)将排在 suffix(i)的前面（这里要求 h[i-1]>1，如果h[i-1]≤1，原式显然成立
并且suffix(k+1)和 suffix(i)的最长公共前缀是h[i-1]-1，
所以suffix(i)和在它前一名的后缀的最长公共前缀至少是 h[i-1]-1。
按照 h[1],h[2],……,h[n]的顺序计算,并利用 h 数组的性质，时间复杂度可以降为 O(n)。
具体实现：实现的时候其实没有必要保存 h 数组，只须按照 h[1],h[2],……,h[n]的顺序计算即可。*/
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++);
/* 另一实现版本（只是将论文中的拆解开而已 便于理解）：
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i; //同上
for(i=0;i<n;height[rank[i++]]=k){
if(k>0)k--; //由最基本的暴力算法 可知height会随向下比较减小
j=sa[rank[i]-1]; // 利用h[i]>=h[i-1]-1的性质 利用后缀顺序进行比较
for(;r[i+k]==r[j+k];k++); //即此步
}
*/
}
int main(){
scanf("%s",s);
n=strlen(s);
da(s,sa,n+1,257);
calheight(s,sa,n);
for(int i=0;i<n;i++)
printf("%d ",sa[i+1]+1);
printf("\n");
for(int i=2;i<=n;i++)
printf("%d ",height[i]);
}
```