后缀数组详解

什么是后缀数组

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

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

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

譬如这道题

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

实现它的方法主要有两种:倍增法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();    
}

再补一下调试结果

基数排序

如果你对上面的主体过程有了大致的了解,那么基数排序的过程就不难理解了

在阅读下面内容之前,我希望大家能初步了解一下基数排序

https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F/7875498?fr=aladdin

大致看一下它给出的例子和c++代码就好

先来大致看一下,代码就4行

M:字符集的大小,一共需要多少个桶

tax:元素出现的次数,在这里就是名次出现的次数

第一行:把桶清零

第二行:统计每个名词出现的次数

第三行:做个前缀和(啪,废话)

可能大家会疑惑前缀和有什么用?

利用前缀和可以快速的定位出每个位置应有的排名

具体的来说,前缀和可以统计比当前名次小的元素有多少个。

懒得举例子啦,不懂得去模拟一下第一次排序的过程吧,

第四行:@#¥%……&*

我知道大家肯定看晕了,我们先来回顾一下这几个数组的定义

sa[i]:排名为$i$的后缀的位置 rak[i]:从第$i$个位置开始的后缀的排名 tp[i]:基数排序的第二关键字,意义与sa一样

此时rak数组和tp数组都已经是排好序的,

‘所以我们此时做的就是拿这两个数组来更新sa数组

倒着循环的目的是让靠前的后缀先出现

后记

本蒟蒻也是第一次看这么难的东西。

第一次见这种东西应该是去年夏天吧,那时我记得自己在机房里瞅着这几行代码看了一晚上也没看出啥来。

现在再来看也是死磕了一天多才看懂。

不过我还是比较好奇。

这种东西是谁发明的啊啊啊啊啊脑洞也太大了吧啊啊啊啊啊啊

哦对了,后缀数组还有一个非常有用的数组叫做Height,这个数组更神奇,,有空再讲吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏女程序员的日常

虚函数&多态

对于经常被问到的虚函数和多态的问题,发现百度百科回答得十分详细,所以自己在百度百科上的解释进行总结 一、虚函数 (1)虚函数简介:在某基类中声明为virtua...

23810
来自专栏从流域到海域

《笨办法学Python》 第29课手记

《笨办法学Python》 第29课手记 本节课讲if语句。 本节内容比较简单,如果觉得你的代码没有错误,但运行时报错,那么你的代码肯定有错误。相信我解释器是已经...

21160
来自专栏程序员叨叨叨

6.8 控制流语句(Control Flow Statement)

程序最小的独立单元是语句(statement),语句一般由分号结尾,缺省情况下,语句是顺序执行的,但是当涉及逻辑判断控制时,就要求有控制流程序语句。控制流程序语...

29030
来自专栏Android机动车

设计模式——工厂方法模式

工厂方法模式,又称工厂模式、多态工厂模式和虚拟构造器模式,通过定义工厂父类负责定义创建对象的公共接口,而子类则负责生成具体的对象。

8720
来自专栏算法channel

一道伤脑筋的算法题 亮了

一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

8300
来自专栏zhisheng

运算优先级、结合性、求值顺序、副作用和顺序点

标题中这几个概念,是很多C/C++程序员在表达式上容易出问题或不清楚的地方,虽然这些概念在很多语言都有体现,但C里面特别明显,所以就以C语言为例子总结下 运算...

53570
来自专栏小詹同学

Leetcode打卡 | No.23 合并 k 个有序链表

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

16210
来自专栏AI2ML人工智能to机器学习

Python的map函数理解四式

这个map函数是python的内嵌的函数, 那么如何手写一个自己的map函数, 实现内嵌map函数一模一样的功能呢?

12520
来自专栏AzMark

Python字符串

19450
来自专栏我杨某人的青春满是悔恨

关于数据结构的一点唠叨

现在大部分高级编程语言的标准库都会提供几种常用的数据结构,诸如线性表、链表、栈、队列、哈希表等等,可以满足日常开发中的大部分需求,开发人员只要调用接口就行了。这...

13740

扫码关注云+社区

领取腾讯云代金券