后缀数组

求后缀数组的rank[],sa[]

• 思路倍增优化

• 以上一次排序为第一关键字,排序后的后一位(即字符串中s[i+\(2^k\)])为第二关键字
• 越界的\(i+2^k\)即可用后缀0进行处理,就可以将每一个后缀子串进行基数排序
• 其中一种高效程序如下所示,详见代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int Max=1000001;
string s;int n;
int rnk[Max],sa[Max];
int tmp[Max],c[Max];

void sarank()
{
    int na=256;//ASCII码中最大值是256 
    memset(c,0,na*sizeof(int));//给C数组清零 
    n=s.size();//取出字符串的长度 
    s[n]=0;n++;//在字符串后加一个后缀,方便倍增优化和比较 
    for(int i=0; i<n; i++)
    {
        rnk[i]=(int)s[i];//每个字符的字典序即为初始排名 
        c[rnk[i]]++;//记录每个排名的个数 
    }//初始化rank[]名次 
    //类似于以下排名模式
    //a a a b b b b c c c c 0 
    //1 1 1 2 2 2 2 3 3 3 3 0
    for(int i=1; i<na; i++) c[i]=c[i]+c[i-1];
    //求前缀和,此时c[]数组即为第i个字符(或字符串)的排名
    //类似于以下排名模式,算并列之后的最小名次 
    //a a a b b b b c  c  c  c  0 
    //3 3 3 7 7 7 7 11 11 11 11 1 
    for(int i=0; i<n; i++)//循环字符串0~n-1 
        sa[--c[rnk[i]]]=i;
    //按照从左到右该字符串由大到小（也可以由小到大）的顺序给字符串排名
    //sa[]类似于以下排名模式,名次从零开始 
    //a a a b b b b c  c c c 0
    //2 1 0 6 5 4 3 10 9 8 7 0
    //此时c[]数组又为第i个字符(或字符串)的排名
    //类似于以下排名模式
    int j;
    for(int len=1; len<n; len=len<<1)//倍增 
    {
        for(int i=0; i<n; i++)//循环名次0~n-1 
        {
            j=sa[i]-len;//下一次字符的位置 
            if(j<0) j=j+n;//由于加入后缀,越界的第二关键字相当于赋为零 
            tmp[c[rnk[j]]++]=j;
            //第一关键字名次已经得出,即为下表c[],每次++即可得到第二关键字的总排名
        }
        //此时,按照从左到右该字符串由小到大的顺序给字符串排名
        //tmp[]类似于以下排名模式,名次从零开始,记录下标 
        //rank[]a a a b b b b c c c c 0
        //      1 1 1 2 2 2 2 3 3 3 3 0
        //c[]   a a a b b b b c c c c 0 
        //      0 0 0 3 3 3 3 7 7 7 7 0
        //tmp[] aa aa ab bb bb bb bc cc cc cc c0 0a
        //      0  1  2  3  4  5  6  7  8  9  0  0
        sa[tmp[c[0]=0]]=j=0;//排名第0的总排名第0 
        for(int i=1; i<n; i++)//
        {
            if(rnk[tmp[i]]!=rnk[tmp[i-1]]||rnk[tmp[i]+len]!=rnk[tmp[i-1]+len])
            //如果第一关键字和第二关键字不同,必为下一名次 
                c[++j]=i;//预处理,本次总排名即为下一次第一关键字的排名 
            sa[tmp[i]]=j;//排名第tmp[i]的总排名第j 
        }
        //此时sa[]类似于以下排名模式,上一个循环相当于错开名次 
        //sa[]  aa aa ab bb bb bb bc cc cc cc c0 0a
        //      0  1  2  3  3  3  4  5  5  5  0  0
        memcpy(rnk,sa,n*sizeof(int));
        memcpy(sa,tmp,n*sizeof(int));
        //依据后缀数组的定义,此时sa[]相当于rank[],tmp[]相当于sa[],交换赋值 
        if(j>=n-1)  break;//如果名次全不相同,已经求完了 
    }
}

int main()
{
    cin>>s;//输入字符串 
    sarank();//求sa[],rank[] 
    cout<<"sa[i]:";for(int i=1; i<n; i++)   printf("%d ",sa[i]+1);printf("\n");
    //注意下标 1~n sa[0]是后缀,由于下标从零开始,下标+1 
    cout<<"rnk[i]:";for(int i=0; i<n-1; i++)    printf("%d ",rnk[i]);printf("\n");
    //注意下标 0~n-1 rnk[n-1]是后缀,由于名次从零开始,但后缀占一个名次,不用加1 
    return 0;
}

后缀数组

原文：https://www.cnblogs.com/vasairg/p/12206572.html