后缀数组总结

· · 算法·理论

后缀数组本体

定义：

首先我们有一个字符串 s（下标从 1 到 n ）

后缀，也就是 suff(i) ：表示从第 i 个字符开始到第 n 个字符结束这些字符所构成的子串。

我们定义一个数组 sa ，sa[i] 表示所有后缀按字典序从小到大排序后，排在第i位的后缀的起点位置，sa 就是我们的后缀数组。

计算：

显然对字符串使用 sort 并不是什么明智的行为，所以我们考虑更加高(li)效(pu)的计算方式~

算法流程：

//原始字符串：acbacab
//采用倍增的思想
int k=//当前关键字长度 

k=0 //显然一切还没开始 
//先将各后缀第一个字符的ascii作为第一关键字，第二关键字都为0 
97 0 [a][](cbacab)
99 0 [c][](bacab)
98 0 [b][](acab)
97 0 [a][](cab)
99 0 [c][](ab)
97 0 [a][](b)
98 0 [b][]()

//排序并赋予每个关键字排名
1 [a][](cbacab)
1 [a][](cab)
1 [a][](b)
2 [b][](acab)
2 [b][]() 
3 [c][](bacab)
3 [c][](ab)

k=1//我们成功得到了所有长度为1的关键字 
//对于每个后缀，它的第一关键字不变，第二关键字为在原字符串中第一关键字后面的那一个关键字
1 3 [a][c](bacab)
1 3 [a][c](ab)
1 2 [a][b]()
2 1 [b][a](cab)
2 0 [b][]() 
3 2 [c][b](acab)
3 1 [c][a](b)

//因为所有关键字的排名我们都已经知道，所以直接按排名进行排序 
1 2 [a][b]()
1 3 [a][c](bacab)
1 3 [a][c](ab)
2 0 [b][]() 
2 1 [b][a](cab)
3 1 [c][a](b)
3 2 [c][b](acab)

//将第一、二关键字合并 
[ab][]()
[ac][](bacab)
[ac][](ab)
[b][]() 
[ba][](cab)
[ca][](b)
[cb][](acab) 

//赋予关键字新的排名 
1 [ab][]()
2 [ac][](bacab)
2 [ac][](ab)
3 [b][]() 
4 [ba][](cab)
5 [ca][](b)
6 [cb][](acab) 

k=2//我们成功得到了所有长度为2的关键字 
//还是像以前一样，获取第二关键字 
1 0 [ab][]()
2 4 [ac][ba](cab)
2 1 [ac][ab]()
3 0 [b][]() 
4 5 [ba][ca](b)
5 3 [ca][b]()
6 2 [cb][ac](ab)

//排序
1 0 [ab][]()
2 1 [ac][ab]()
2 4 [ac][ba](cab)
3 0 [b][]() 
4 5 [ba][ca](b)
5 3 [ca][b]()
6 2 [cb][ac](ab)

//将第一、二关键字合并 
[ab][]()
[acab][]()
[acba][](cab)
[b][]() 
[baca][](b)
[cab][]()
[cbac][](ab)

//赋予每个关键字新的排名
1 [ab][]()
2 [acab][]()
3 [acba][](cab)
4 [b][]() 
5 [baca][](b)
6 [cab][]()
7 [cbac][](ab)

//发现所有排名都不重复了，程序结束
//当然如果还有重复，就继续循环k=4，k=8，k=16……

代码：

#include<bits/stdc++.h>
using namespace std;
int n,sa[1000010],tmp[1000010],id[1000010];
char s[1000010];
struct node
{
    int id,a,b;
    //id：后缀的起始下标 
    //a：第一关键字 b：第二关键字 
}o[1000010];
bool cmp(node x,node y)
{
    if(x.a<y.a) return true;
    else if(x.a==y.a&&x.b<y.b) return true;
    return false; 
}
void Sort()//顾名思义，按照第一、第二关键字进行排序 
{
    sort(o+1,o+n+1,cmp);
    for(int i=1;i<=n;i++)//id[i]表示下标为i的关键字在o数组中的位置 
        id[o[i].id]=i;
    return;
}
bool renew()//赋予每个关键字新的排名 
{ 
    int cnt=0; o[0].a=-1;
    for(int i=1;i<=n;i++)
    {
        if(o[i].a!=o[i-1].a||o[i].b!=o[i-1].b)
            cnt++;//如果和前面不一样，排名后延，如果一样，和前面使用相同排名 
        tmp[i]=cnt;//因为o[i].a还得用，所以把新的排名暂存一下 
    }
    for(int i=1;i<=n;i++)
        o[i].a=tmp[i];//获取暂存的排名，完成一二关键字合并 
    if(cnt==n) return true;//排名无重复，可以结束程序 
    else return false;
}
void getsa()
{
    for(int i=1;i<=n;i++)//第一遍将ascii码作为关键字排序 
    {
        o[i].id=i;
        o[i].a=(int)s[i]; o[i].b=0;
    }
    Sort(); renew();
    for(int k=1;k<=n;k*=2)//当前关键字长度为k 
    {
        for(int i=1;i<=n;i++)
        {
            if(o[i].id+k<=n)//对于以o[i].id为起始下标的后缀，如果在s中有紧随其(第一)关键字之后的关键字 
                o[i].b=o[id[o[i].id+k]].a;//将此关键字作为后缀的第二关键字 
            else o[i].b=0;//否则补0 
        }
        Sort();//排序并更新 
        if(renew()) break;//直到没有重复的排名 
    }
    for(int i=1;i<=n;i++)
        sa[i]=o[i].id;//sa[i]表示排名为i的关键字的起始下标 
    return;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    getsa();
    for(int i=1;i<=n;i++)
        printf("%d ",sa[i]);
    return 0;
}

时间复杂度：O(n log^2 n )

如果把双关键字的排序方式从快排改为基数排序，复杂度可以做到 O(n log n )，但会有空间问题，而且原来的时间复杂度已经足够做出大部分题了，所以没啥用。

queue<node> q[100010];//不敢多开，会爆空间
void Sort()
{
    int Max=0;
    for(int i=1;i<=n;i++)
    {
        q[o[i].b].push(o[i]);
        Max=max(Max,o[i].b);
    }
    int cnt=0;
    for(int i=0;i<=Max;i++)
    {
        while(!q[i].empty())
        {
            o[++cnt]=q[i].front();
            q[i].pop();
        }
    }
    Max=0;
    for(int i=1;i<=n;i++)
    {
        q[o[i].a].push(o[i]);
        Max=max(Max,o[i].a);
    }
    cnt=0;
    for(int i=0;i<=Max;i++)
    {
        while(!q[i].empty())
        {
            o[++cnt]=q[i].front();
            q[i].pop();
        }
    }
    for(int i=1;i<=n;i++)
        id[o[i].id]=i;
    return;
}

所以就可以做：P3809 【模板】后缀排序 和 P4051 [JSOI2007]字符加密还有P2870 [USACO07DEC]Best Cow Line G

（ sort 开 O2 能提速4倍）