后缀数组与应用

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

一、后缀数组

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

1.1 \(\quad\) 约定与定义

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

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

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

不难发现，上面两个函数互为反函数，即： \[ \begin{aligned} sa[rk[i]]=i\\ rk[sa[i]]=i \end{aligned} \]

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

\[ ht[i]=\text{LCP}(sa[i],sa[i-1]) \]

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

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

\[ h[i]=height[rk[i]] \]

例子 \(\quad\) 给定字符串 \(s=aabaaaab\)，其后缀数组、名次数组、高度数组、公共前缀数组为别为： \[ \begin{array}{} &1&2&3&4&5&6&7&8\\ s:&a&a&b&a&a&a&a&b\\ sa:&4&5&6&1&7&2&8&3\\ rk:&4&6&8&1&2&3&5&7\\ height:&0&3&2&3&1&2&0&1\\ h:&3&2&1&0&3&2&1&0 \end{array} \]

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]]
    }
}