后缀数组

后缀数组代码及注释

// 后缀数组 
#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]);
}

发表于 2018-05-24 19:11:05 in 字符串