SuffixSort

后缀数组前置知识

后缀排序$(SuffixSort)$,是后缀数组的核心部分,但我不知道这玩意儿到底是怎么想出来的……(毕竟我不是神仙).然后,这个东西并不是很难理解,我认为难的地方其实是在$height_i$的理解.所以….$height$我到现在也没理解.

先说一说后缀排序.

后缀排序是对后缀进行排序,这有啥用呢?如果没有$height$,后缀数组就失去了它的魅力.但单纯的后缀排序也并非没有用.哎?不对,好像确实没啥用…但是这不影响我们学它.

后缀排序是对一个串的所有后缀进行排序,排序依据就是字典序.

一个显然的想法是把所有后缀都拿出来排一遍序,但显然这亚子太慢了,复杂度高达 $O(nl \log_2{n})$ 最好也只能是 $O(nl)$.因为字符串的比较是$O(L)$的.那么考虑怎样去优化这个排序.

我们可以发现,每次字符串的比较,如果我们知道这两个字符串相对应的两半的大小关系,那么我们可以直接得到这两个字符串的大小关系(类比线段的两个关键字的排序).这样是可以做到$O(1)$判断大小的.

那么我们这里就可以比较自然的想到使用倍增算法.我们先对所有的单个字符进行排序,这是$O(n \log_2{n})$的,这个复杂度可以接受,然后我们再对长度为$2$的串进行排序,以上一次排完序的单个字符大小关系为关键字.再对长度为$4$的串进行排序……以此类推.显然,最后我们一定能得到所有后缀的排序结果.

于是我们就倍增地枚举串的长度,进行排序,复杂度为$O(n \log_2^2 {n})$.这样的复杂度已经足以应对不太刁钻的数据.

但是我们很可能仍然不满足于这样的复杂度.

我们注意到,对于字符串的排序,字符集一般不会太大,这也就告诉我们,基数排序或许是可行的.

事实上,多数情况下,都是可以使用基数排序的.

于是我们考虑基数排序,这其实就是桶排的强化版?或许就是桶排吧…

我们设桶数组是$cnt$,那么$pos$对应的前缀和就是$pos$的排名.

要知道的是,基数排序是稳定排序.

于是我们把整个后缀排序的复杂度降至$O(n \log_2{n})$.

$sa[i]:$第 $i$ 小的后缀的编号.

$rank[i]:$编号为 $i$ 的后缀的排名(从小到大).

于是总的代码长成这个亚子:

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)
#define per(i,a,b) for (int i = a ; i >= b ; -- i)

const int N = 2e6 + 100 ;

typedef int one[N] ;

one trk , rk , SA , tmp , h , cnt ;
int n , p ; char s[N] ;

inline void SuffixSort () {
    p = 0 ; rep ( i , 1 , n ) p = std::max ( (int)s[i] , p ) ;
    rep ( i , 1 , n ) ++ cnt[s[i]] ;
    rep ( i , 1 , p ) cnt[i] += cnt[i-1] ;
    per ( i , n , 1 ) SA[cnt[s[i]]--] = i ;
    rk[SA[1]] = p = 1 ;
    rep ( i , 2 , n ) rk[SA[i]] = ( s[SA[i]] == s[SA[i-1]] ? p : ++ p ) ;

    for (int w = 1 ; w <= n ; w <<= 1) {
        MEM ( cnt , 0 ) ;
        rep ( i , 1 , n ) ++ cnt[rk[i+w]] ;
        rep ( i , 1 , p ) cnt[i] += cnt[i-1] ;
        per ( i , n , 1 ) tmp[cnt[rk[i+w]]--] = i ;

        MEM ( cnt , 0 ) ;
        rep ( i , 1 , n ) ++ cnt[rk[i]] ;
        rep ( i , 1 , p ) cnt[i] += cnt[i-1] ;
        per ( i , n , 1 ) SA[cnt[rk[tmp[i]]]--] = tmp[i] ;

        trk[SA[1]] = p = 1 ;
        rep ( i , 2 , n ) trk[SA[i]] = ( rk[SA[i]] == rk[SA[i-1]] && rk[SA[i]+w] == rk[SA[i-1]+w] ) ? p : ++ p ;
        rep ( i , 1 , n ) rk[i] = trk[i] ;
    }
}

这一份代码是参考了 $RXD$ 大爷的代码.

height数组

后缀数组的核心

$height[i]:$第 $i$ 小的后缀和第 $i-1$小的后缀的最长公共前缀，

即 $LCP(suffix[sa[i]],suffix[sa[i-1]])$

任意两个后缀的最长公共前缀?设为后缀 $x$ 和后缀 $y$，其中

$rank[x] < rank[y]$。答案就是

$$\min_{(rank[x],rank[y]]}{height[i]}$$

如果已经求出了$height$,用$ST$表就可以$O(n \: log_2 n)$预处理，

$O(1)$回答两个后缀的最长公共前缀.

对于$height$数组:

有性质$:height[rank[i]] ≥ height[rank[i-1]]-1$

如果 $height[rank[i-1]] = 0$ 显然成立，否则在 $i-1$ 这个后

缀与它前驱的 $LCP$ 的基础上去掉第一个字符，就找到了一个后

缀与 $i$ 这个后缀的 $LCP≥ height[rank[i-1]]-1$.

进而有 $height[rank[i]] ≥ height[rank[i-1]]-1$

于是按照原串的顺序求 $height$ 就能做到线性了.

以上内容来自$R$爷.(我还是不太懂的…放在这里是为了以后方便复习.)

所以代码长这样:

for (int i = 1 , j = 0 ; i <= n ; ++ i) {
    if ( rk[i] == 1 ) continue ;
    while ( s[i+j] == s[SA[rk[i]-1]+j] ) ++ j ;
    h[rk[i]] = j ; if ( j ) -- j ;
}