首页 > > 程序设计 > C/C++ >

后缀数组详解

2018-06-17 21:17:37来源：未知阅读 ()

什么是后缀数组

后缀数组是处理字符串的有力工具 —罗穗骞

个人理解：后缀数组是让人蒙逼的有力工具！

就像上面那位大神所说的，后缀数组可以解决很多关于字符串的问题，

譬如这道题

注意：后缀数组并不是一种算法，而是一种思想。

实现它的方法主要有两种：倍增法$O(nlogn)$ 和 DC3法$O(n)$

其中倍增法除了仅仅在时间复杂度上不占优势之外，其他的方面例如编程难度，空间复杂度，常数等都秒杀DC3法

我的建议：深入理解倍增法，并能熟练运用（起码8分钟内写出来&&没有错误）。DC3法只做了解，吸取其中的精髓；

但是由于本人太辣鸡啦，所以本文只讨论倍增法

前置知识

后缀

这个大家应该都懂吧。。

比如说$aabaaaab$

它的后缀为

基数排序

我下面会详细讲

现在，你可以简单的理解为

基数排序在后缀数组中可以在$O(n)$的时间内对一个二元组$(p,q)$进行排序，其中$p$是第一关键字，$q$是第二关键字

比其他的排序算法都要优越

倍增法

首先定义一坨变量

$sa[i]$：排名为$i$的后缀的位置

$rak[i]$：从第$i$个位置开始的后缀的排名，下文为了叙述方便，把从第$i$个位置开始的后缀简称为后缀$i$

$tp[i]$：基数排序的第二关键字，意义与$sa$一样

$tax[i]$：$i$号元素出现了多少次。辅助基数排序

$s[i]$：字符串

可能大家觉得$sa$和$rak$这两个数组比较绕，没关系，多琢磨一下就好

事实上，也正是因为这样，才使得两个数组可以在$O(n)$的时间内互相推出来

具体一点

$rak[sa[i]]=i$

$sa[rak[i]]=i$

那我们怎么对所有的后缀进行排序呢？

我们把每个后缀分开来看。

开始时，每个后缀的第一个字母的大小是能确定的，也就是他本身的ASCLL值

具体点？把第$i$个字母看做是$(s[i],i)$的二元组，对其进行基数排序

这样我们就得到了他们的在完成第一个字母的排序之后的相对位置关系

接下来呢？

不要忘了，我们算法的名称叫做“倍增法”，每次将排序长度*2，最多需要$log(n)$次便可以完成排序

因此我们现在需要对每个后缀的前两个字母进行排序

此时第一个字母的相对关系我们已经知道了。

那第二个字母的大小呢？我们还需要一次排序么？

其实大可不必，因为我们忽略了一个非常重要的性质：第$i$个后缀的第二个字母，实际是第$i+1$个后缀的第一个字母

因此每个后缀的第二个字母的相对位置关系我们也是知道的。

我们用$tp$这个数组把他记录出来，对$(rak,tp)$这个二元组进行基数排序

接下来我们需要对每个后缀的前四个字母组成的字符串进行排序

此时我们已经知道了每个后缀前两个字母的排名，而第$i$个后缀的第$3,4$个字母恰好是第$i+2$个后缀的前两个字母。

他们的相对位置我们又知道啦。

这样不断排下去，最后就可以完成排序啦

我相信大家看到这里肯定是一脸mengbi

下面我结合代码和具体的排序过程给大家演示一下

过程详解

还是以上面的图片为例

按照上面说的，开始时$rak$为字符的ASCLL码，第二关键字为它们的相对位置关系

这里的$a$数组是字符串数组

然后我们对其进行排序，我们暂且先不管它是如何进行排序，因为排序的过程非常难理解，一会儿我重点讲一下。

排完序之后各个后缀的位置关系是这样的

各个数组的大小

然后我们进行倍增。

这里再定义几个变量

$M$：字符集的大小，基数排序时会用到。不理解也没关系

$p$：排名的多少(有几个不同的后缀)

注意在排序的过程中，各个后缀的排名可能是相同的。因为我们在倍增的过程中只是对其前几个字符进行排名。

但是，对于每个后缀来说，最终的排名一定是不同的！毕竟每个后缀的长度都不相同

下面是倍增的过程

$w$表示倍增的长度，当各个排名都不相同时，我们便可以退出循环。

$M=p$是对基数排序的优化，因为字符集大小就是排名的个数

这两句话是对第二关键字进行排序

此时的$p$并不是统计排名的个数，只是一个简单的计数器

注意：有一些后缀是没有第二关键字的，他们的排名应该在最前面。

这对应第$35$行，不要忘了$tp[i]$的含义：排名为$i$的后缀的位置

注意第$36$行：如果$sa[i]$位置的后缀的第一关键字排名靠前，实际上代表着$sa[i]-1$位置的后缀的第二关键字排名靠前（比较难理解，大家好好琢磨一下）

此时第一二关键字都已经处理好了，我们进行排序

排完序之后，我们得到了一个新的$sa$数组

此时我们用$sa$数组来更新$rak$数组

我们前面说过$rak$数组是可能会重复的，所以我们此时用$p$来表示到底出现了几个名次

还需要注意一个事情，在判断是否重复的时候，我们需要用到上一轮的$rak$

而此时$tp$数组是没有用的，所以我们直接交换$tp$和$rak$

当然你也可以写为

在判断重复的时候，我们实际上是对一个二元组进行比较。

当满足判断条件时，两个后缀的名次一定是相同的（想一想，为什么？）

然后愉快的输出就可以啦！

放一下代码

// luogu-judger-enable-o2
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e6+10;
int sa[MAXN],tax[MAXN],rak[MAXN],tp[MAXN],a[MAXN],N,M;
char s[MAXN];
void debug()
{
    printf("*****************\n");
    printf("下标");for(int i=1;i<=N;i++) printf("%d ",i);printf("\n");
    printf("sa  ");for(int i=1;i<=N;i++) printf("%d ",sa[i]);printf("\n");
    printf("rak ");for(int i=1;i<=N;i++) printf("%d ",rak[i]);printf("\n");
    printf("tp  ");for(int i=1;i<=N;i++) printf("%d ",tp[i]);printf("\n");
}
void Qsort()
{
    for(int i=0;i<=M;i++) tax[i]=0;
    for(int i=1;i<=N;i++) tax[rak[i]]++;
    for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
    for(int i=N;i>=1;i--) sa[ tax[rak[tp[i]]]-- ]=tp[i];
}
void Ssort()
{
    M=127;
    for(int i=1;i<=N;i++) 
        rak[i]=a[i],tp[i]=i;
    Qsort();

    debug();
    for(int w=1,p=1; p<N ; M=p,w<<=1)
    {
        p=0;
        for(int i=1;i<=w;i++) tp[++p]=N-w+i;
        for(int i=1;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;  
        Qsort();
        swap(rak,tp);
        rak[sa[1]]=p=1;
        for(int i=2;i<=N;i++) 
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
        debug();
    }
    for(int i=1;i<=N;i++) printf("%d ",sa[i]);
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    scanf("%s",s);
    N=strlen(s);
    for(int i=0;i<N;i++) a[i+1]=s[i]-48;
    Ssort();    
}