后缀数组与应用

后缀数组 (Suffix Array) 是处理字符串问题的有力工具之一，通常利用后缀数组 $sa$ 处理字符串子串与后缀串排序、公共前缀等问题。

一、后缀数组

通过计算后缀数组与排名数组，辅助解决系列问题。

1.1 $\quad$ 约定与定义

对于一个长度为 $n$ 的字符串 $s$，我们定义 $s_i\dots s_n$ 构成的子串为 $s$ 在 $i$ 位置上的后缀，下面给出几个函数的定义：

  • $sa_i$：后缀数组。表示 $s$ 的所有后缀串中，按字典序排名，第 $i$ 小的后缀串的起始位置。

  • $rk_i$：名次数组。表示起始位置为 $i$ 的后缀串的排名（按字典序）。

不难发现，上面两个函数互为反函数，即：

  • $height_i$：高度数组。表示排名为 $i$ 的后缀串与排名为 $i-1$ 的后缀串的最长公共前缀。特殊地，$height_1=0$，因为没有比它排名小的后缀串。形式化地：

其中，$\text{LCP}(s,t)$ 表示字符串 $s,t$ 的最长公共前缀。

  • $h_i$：公共前缀数组。表示起始位置为 $i$ 的后缀串，与比其排名小 $1$ 的后缀串的最长公共前缀，即：

例子 $\quad$ 给定字符串 $s=aabaaaab$，其后缀数组、名次数组、高度数组、公共前缀数组为别为：

1.2 $\quad$ 后缀数组的计算

前置芝士：倍增法、基数排序。

我们有暴力的做法，对所有后缀串排序，但是这个复杂度并不优秀。

我们考虑倍增地计算后缀数组。也就是说，每次我们计算一段长形如 $[i,i+2^k-1]$ 的子串，而后合并前后两个子串，并按照两个子串的各自的关键字进行排序合并。下面我们考虑怎样合并两个已经排好序的更小的子串，使其拼成一个更长的、有序的子串，进而贡献给后缀数组。如下图：

这张图中，我们进行了 $O(\log n)$ 次倍增。第一次，我们就以字典序为前后两个关键字合并。其后，我们分别以前面一段的名次、后面一段的名次，为两个关键字进行合并。我们每一次合并需要对 $n$ 个数的两个关键字排序，直接使用快速排序可以获得 $O(n\log^2 n)$ 的复杂度。一定程度上可以接受，但是不是很优秀，我们希望消去一个 $\log$ 的复杂度。

考虑使用基数排序替换快速排序，每次先对第二关键字开桶记录，而后对第一关键字开桶记录。这样我们放入第一关键字桶的顺序已经满足排序顺序，换句话说，已经满足第二关键字递增的顺序。

时间复杂度 $O(n\log n)$。

1.3 $\quad$ 代码实现

定义以下变量：

  • $m$：桶中最大元素，即桶的上限；
  • $c_i$：数组为计数桶。
  • $x_i$：起始位置为 $i$ 的串的第一关键字；
  • $y_i$：第二关键字排名为 $i$ 的串的起始位置，即 $x$ 的位置。

下面描述算法流程。

  1. 对于第一次递增，我们直接按照每单个字符排序，将每个长度为 $1$ 的串的第一关键字放入桶中。

  2. 然后对桶 $c$ 进行前缀和处理，这样我们确定了第一关键字为 $k$ 的元素最大排在第几名。

  3. 我们对后缀数组进行第一次赋值，表示长度为 $1$ 的后缀串排名第 $i$ 的串的起始位置为 $sa_i$。这里注意需要倒序枚举 $i$，因为我们只划定了排序名次的上界。确切的名次需要由上界依次递减得到。

  4. 而后我们进行更多次的倍增，处理长度为 $k$ 的串。考虑到如果合并两个串时，第一个串的起始位置 $i\ge n-k+1$，我们第二个串就是空串，需要提前处理。而且这些串合并后，排名一定比第二个串非空的靠前。下面的 $num$ 表示第二关键字排名。注意 $y$ 数组保存的是对应的第一关键字的位置。

  5. 而后我们对于所有可能的第二串加入 $y$ 数组。只有 $sa[i]> k$ 时才可行（短于倍增长度无法找到第一串）。

  6. 仿照第一次倍增的思路处理第一关键字桶。

  7. 基数排序，因为 $y$ 的顺序是按照第二关键字的顺序来排的，第二关键字靠后的，在同一个第一关键字桶中排名越靠后。

  8. 清空第一关键字数组，并根据当前值重新赋关键字。注意到此时我们直接按后缀数组赋值即可，本身有序。更新桶上限 $m$。

完整代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Suffix_Array(){
    cin>>(s+1);                                                       //Step.1
    n=strlen(s+1);
    m='z';
    for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
    for(int i=2;i<=m;i++) c[i]+=c[i-1];                               //Step.2
    for(int i=n;i;i--) sa[c[x[i]]--]=i;                               //Step.3
    for(int k=1;k<=n;k<<=1){                                          //Step.4
        int num=0;
        for(int i=n-k+1;i<=n;i++) y[++num]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;           //Step.5
        for(int i=1;i<=m;i++) c[i]=0;                                 //Step.6
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=2;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];                     //Step.7
        for(int i=1;i<=n;i++) lstx[i]=x[i],x[i]=0;                    //Step.8
        num=1;
        x[sa[1]]=1;
        for(int i=2;i<=n;i++){
            if(lstx[sa[i]]==lstx[sa[i-1]]&&lstx[sa[i]+k]==lstx[sa[i-1]+k]) x[sa[i]]=num;
            else x[sa[i]]=++num;
        }
        m=num;
    }
}

二、子串最长公共前缀

我们记 $\text{LCP}(i,j)$ 表示字符串排名为 $i$ 的后缀串，和排名为 $j$ 的后缀串的最长公共前缀，根据性质计算。

2.1 $\quad$ 基本性质

性质 1 $\quad$ $\text{LCP}(i,j)=\text{LCP}(j,i)$。

性质 2 $\quad$ $\text{LCP}(i,i)=\text{len}(sa[i])=n-sa[i]+1$。其中，$\text{len(i)}$ 表示起始位置为 $i$ 的后缀串的长度。

上面两个性质显然。

性质 3 $\quad$ $\forall 1\le i\le j\le k\le n\ ,\ \text{LCP}(i,k)=\min(\text{LCP}(i,j),\text{LCP}(j,k))$ 。

因为是按照后缀排序的，所以易证。

进而得出，按照后缀排完序的后缀串，两个后缀串的最长公共前缀就等于 $height_{i+1}\cdots height_j$ 取最小值。
性质 4 $\quad$ $\forall 1<i\le j\le k\le n\ ,\ \text{LCP}(i,k)=\min(\text{LCP}(j,j-1))$。

性质 5 $\quad$ $h_i\ge h_{i-1}-1$，这是关键性质。

考虑粗略证明性质5。令第 $i-1$ 位为字符 $s$，则 $i-1$ 位置的后缀为 $sX$，$i$ 位置的后缀为 $X$。

我们找到后缀排名在 $sX$ 前一名的后缀，即 $sa[rk[i-1]-1]$，记 $k$ 为这个排名。这两个后缀的最长公共前缀就是 $height[rk[i-1]]$。分成两类情况讨论：

  • 如果第 $k$ 个串和第 $i-1$ 个串第一个字符不同，即没有公共前缀，即 $height[rk[i-1]]=0$，一定有 $height[rk[i]]\ge height[rk[i-1]]+1$，即 $h[i]\ge h_[i-1]-1$。
  • 如果第 $k$ 个串和第 $i-1$ 个串第一个字符相同，可以表示第 $k$ 个串为 $sY$。一定有 $sY<sX\Rightarrow Y<X$。那么第 $k+1$ 个字符串要排名在 $i$ 前面。那么第 $k+1$ 个字符串和 $i$ 的最长公共前缀就是 $height[rk[i-1]]-1$。根据性质4可得 $h[i]\ge h[i-1]=1$。

2.2 $\quad$ 后缀排序最长公共前缀的计算

我们利用性质5计算后置排序后的 $height$ 数组和 $h$ 数组。

1
2
3
4
5
6
7
8
9
void getheight(){
    for(int i=1;i<=n;i++) rnk[sa[i]]=i;
    for(int i=1,j=0;i<=n;i++){
        if(rnk[i]==1) continue;
        if(j) j--;
        while(i+j<=n&&sa[rnk[i]-1]+j<=n&&s[i+j]==s[sa[rnk[i]-1]+j]) j++;
        heigh[rnk[i]]=j;                  //h[i]=height[rnk[i]]
    }
}