【后缀数组】请把你的蓝书翻到第221页

上课了。

同学们请把你们的《算法竞赛入门经典·训练指南》翻到第221页。

映入眼帘的应该是这样的东西:

char s[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],n;
void build_sa(int m){
  int *x=t,*y=t2;
  for(int i=0;i<m;i++) c[i]=0;
  for(int i=0;i<n;i++) c[x[i]=s[i]]++;
  for(int i=1;i<m;i++) c[i]+=c[i-1];
  for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
  for(int k=1;k<=n;k<<=1){
    int p=0;
    for(int i=n-k;i<n;i++) y[p++]=i;
    for(int i=0;i<n;i++)
      if(sa[i]>=k) y[p++]=sa[i]-k;
    for(int i=0;i<m;i++) c[i]=0;
    for(int i=0;i<n;i++) c[x[y[i]]]++;
    for(int i=0;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
    swap(x,y);
    p=1;
    x[sa[0]]=0;
    for(int i=1;i<n;i++)
      x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
    if(p>=n) break;
    m=p;
  }
}

不得不说,这个世界上比看懂刘汝佳dalao的代码更难的事情大概只有进C9了。

咳咳,开始正题。

我假设你已经把第220页的东西读完了,并且觉得这个排序方法非常棒。

我们来看第一段代码。

刘汝佳dalao给的注释是:

基数排序

我假设你已经查阅过基数排序的有关资料,并且觉得这个东西还可以理解。

开始解释。

第一行:

for(int i=0;i<m;i++) c[i]=0;

让我们猜想一下c数组是什么东西。看看下面几行代码,c数组很像一个“桶”。

第二行:

for(int i=0;i<n;i++) c[x[i]=s[i]]++;

这行代码做了两件事情。第一,它把s数组的值赋给了x数组。

等等,x数组不是int类型的吗?

(……)

这样的强制转换是完全可行的,实际上,char数组存储的就是ASCII码。

第二,增加对应字符(第一关键字)的计数。(有几个第一关键字的值是i

第三行:

for(int i=1;i<m;i++) c[i]+=c[i-1];

这句话求了一个前缀和。可是这样的前缀和有什么用呢?

让我们想想,对于后缀数组的首次排序的依据是什么。

我们应该取第一个字母进行排序。第一关键字是字母。

那第二关键字呢?这里的第二关键字是后缀的起始位置。

大致就是说,字母越大排名越烂,排名越烂数值越大,所以我们需要将这些排名累加,等一下取排名的时候,能够保证不管第二关键字的顺序如何,第一关键字(字母)更优的,排名一定越好。

这个非常特殊,希望你能在这里停一下,确定你搞懂了再往下看。

第四行:

for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;

你的脑内:&%¥¥……&*¥%¥%

好了好了理一下思路。

首先看一看循环的方向:从大到小。

那是要干嘛用?

还有第二关键字到哪里去了?


先看一下x[i]数组。

其实,前面有提到,第二关键字是后缀的起始位置

起点位置不就是i吗?

对呀。其实我们可以先搞一个数组q[i],并且令q[i]=i,这样我们就创造了一个第二关键字数组。然后在写第四行代码的时候,写类似于:

sa[--c[x[q[i]]]]=q[i];

的东西。

但是这个太烦了,所以我们简化一下。

但是为了加深你的理解,之后我会用sa[–c[x[q[i]]]]这样的形式。

好了再回到这行代码上面。看一下x[q[i]]。

q[i]代表的是第二关键字排名为i的后缀的起始位置

我们用第二关键字将所有后缀从最差到最好排序,从差的往好的枚举。

但是第一关键字总比第二关键字重要!所以,得到q[i]之后,我们还要这个位置对应的第一关键字到底是好是坏。

那么,x[q[i]]就代表了第二关键字排名为i的后缀的起始位置对应的第一关键字排名。

念三遍之后再往下看。

好了,第二关键字和第一关键字的情况我们都知道了,那之后怎么给它排名呢?

 

c数组和sa数组这个时候派上了用场。

(先声明,sa数组是排名第i的后缀的起始位置。)

让我们再思考一下循环的方向——从坏到好。

再思考这么两个情景:

①有两个后缀A和B,它们的第一关键字相同,第二关键字A更优。

②有两个后缀A和B,第一关键字B更优,第二关键字A更优。

对于①情景,先被枚举到的是B后缀。那么,B后缀将先从c数组中“拿”一个数来当作它的排名。A后缀将在B数组之后从c数组中“拿”一个数来当做它的排名。

代码里面有两个神圣的字符——

  • –   –

后缀每拿一个排名,后缀的第一关键字对应的c数组中的值就会自减。

再看那两个后缀A和B。现在你知道在sa数组中那个后缀的起始位置对应的排名较小吗?

请自行分析第二个场景。

B的排名应该大于A的排名。

我现在再用一句比较抽象的话来概括这句话的作用:

先按照从坏到好的顺序遍历第二关键字排名,第一关键字更优的就无视第二关键字来赋予排名,第一关键字相同的情况下,根据第二关键字的先后来确定排名。

现在来看后面。

for(int k=1;k<=n;k<<=1){
  int p=0;
  for(int i=n-k;i<n;i++) y[p++]=i;
  for(int i=0;i<n;i++)
    if(sa[i]>=k) y[p++]=sa[i]-k;

我们的算法名字叫做“倍增”,也就是说,每一轮循环中,我们已经算好了按照长度为k后缀的前缀相对关系为依据的后缀的排名(……

现在,我们要根据长度为2k的后缀的前缀的相对关系对后缀进行排名。

多读几遍,多读几遍。

在对2k的长度进行排名时,第一关键字是前k个字符,第二关键字是后k个字符。(若有不懂请看蓝书220页)

对于每一轮,我们都要算第二关键字的排名。

现在,后缀的前缀的长度已经不是1了,它可能很大。

再明确一个目标:

对两个后缀而言,如果它们的长度不相等,但是短的后缀是长的后缀的前缀的话,我们“喜欢”长度比较小的后缀。(这个应该没什么问题吧

试想一下,有的后缀长度太短了,根本没办法达到2k的长度,它们甚至连k的长度都没有。它们的第一关键字(前k个字符)都是“残废”的,怎么可能有第二关键字呢?

但是排序总还是要排的呀。所有的后缀都要有一个第二关键字。而且,一般来说,由于长度比较小,容易有字典序上的优势,在其他条件相同的情况下(就像上面讲的那样),短的后缀一般更优,所以,这些没有第二关键字的后缀们反而在第二关键字排序下有着更高的名次。这些后缀的第二关键字都是相同的,所以也就无所谓排名先后了反正他们的实际长度都不一样,第一关键字会办好事的

处理好这些后缀,再处理别的。

注意下面这行代码:

for(int i=0;i<n;i++)
  if(sa[i]>=k) y[p++]=sa[i]-k;

sa[i]表示的是上一轮排名为i的后缀的起始位置。

上一轮后缀排序是以总长度为k的前缀为依据进行的。

现在我们要得到的排序,依据必须是长为2k的前缀之间的关系。

再看这两行代码。先下结论,我们现在要求的是第二关键字排名为i的长为2k的后缀的前缀起始位置

设想我们找到了长为k,起始位置为sa[i]的排名为i的前缀。我们想把这个前缀当成某个长为2k的前缀的后k个字符(第二关键字)。

但是,如果这个起始位置前面的字符数少于k个,这样的前缀就不存在了。

所以,我们需要让起始位置大于等于k。

再者,我们根据排名从好到坏枚举起始位置,这也保证了排名的单调性。

 

好了,到这里,第二关键字又求完了。接下来的四句话真的和前面第一次排序时候的情况没有什么差别,请自行分析吧!

 

好了,我假定你已经分析完了。

紧接着我们要更新这一次的排名。(x数组)

这一轮的第二关键字在这时候已经没有什么用了,所以我们就把它丢掉。

可是我们又不想浪费空间,所以我们把x数组和y数组交换一下。

现在,y数组存储的是上一轮的最终排名,x数组等待存储这一轮的最终排名。

其实,判断两个后缀排名是否需要赋为相同值的判定方法就是:

在两个后缀的前2k个字符中,先看前k个字符是否相同,再看后k个字符是否相同。

是不是很像废话?但是我打赌你看到这句代码的时候:

x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;

一定没想到这句话就是上面这个意思。

上一轮得出的排名一样,那么这两个字符串就相等咯。

相等,就赋同样的排名,否则赋更差的排名(sa数组的下标在循环中越来越大)。

最后:

if(p>=n) break;
m=p;

p的数值是几,就赋了几个排名。如果各个后缀排名都不相等,排序就结束,退出循环。

排名之后,最多有p种不同的排名,所以下一次排序的时候,字符集大小只需要p了。

 

恭喜你已经理解了这份代码!

或许因为我辣鸡的讲解,你可能还不是很懂。这是一篇讲解的更加完善的blog:

点这儿

“【后缀数组】请把你的蓝书翻到第221页”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注