跳转至

String

  • 分类于 String
  • 需要 4 分钟阅读时间

后缀数组

后缀数组是处理字符串的利器。

定义

对于长度为 \(n\) 的字符串 \(s = s_1 s_2 \cdots s_n\)，定义 \(s[i,j] = s_i s_{i+1} \cdots s_j\)，即 \(s\) 的第 \(i\) 个到第 \(j\) 个字符形成的子串。

定义 sa 为 \(s\) 的后缀数组，sa[i] 表示第 \(i\) 小的后缀的编号。

定义 rk[sa[i]]=i，即 rk[i] 表示后缀 \(i\) 的 rank。

求解

考虑最暴力的做法，取出所有后缀并排序，空间复杂度 \(O(n ^ 2)\)，时间复杂度 \(O(n^2 \log n)\)。

考虑倍增，设 rk[j][i] 表示在所有长度为 \(2^j\) 的后缀中，后缀 \(s[i,i+2^j-1]\) 的 rank（超出 \(n\) 的部分记为空字符，小于任何非空字符）。

显然我们可以 naively 得到 rk[0][i]，考虑如何由 rk[j-1] 得到 rk[j]。

发现可以将所有二元组 (rk[j-1][i],rk[j-1][i+(1<<(j-1))] 排序，即把每段后缀分为前后两段，并以前一半的 rank 作为第一关键字，后一半的 rank 作为第二关键字，超出 \(n\) 的部分记为 0，排序后得到 rk[j]。

总共倍增 \(\mathrm O(\log n)\) 次，每次排序 \(\mathrm O(n \log n)\)，总时间复杂度 \(\mathrm O(n \log^2 n)\)。

发现 rk 的值域是 \(\mathrm O(n)\) 的，因此可以用桶排做到 \(O(n \log n)\)。

在算法竞赛中这已经足够了，如果追求更优的时间复杂度，可以考虑 SA-IS / DC3 算法，线性时间复杂度，但实现十分复杂，在竞赛中不常用，因此不再赘述。

显然通过 rk 可以 \(\mathrm O(n)\) 得到 sa。

height 数组

定义 ht[i] 为后缀 sa[i] 与 sa[i-1] 的最长公共前缀的长度，并设 ht[1]=0。

一眼看来似乎没有线性做法，但是我们将尝试证明以下引理：

Lemma: ht[rk[i]] \(\ge\) ht[rk[i-1]]-1。

Proof:

ht[rk[i-1]] \(\le 1\) 的情况是 naive 的。

若 ht[rk[i-1]] \(\ge 2\)，即 sa[rk[i-1]-1] 与 i-1 的最长公共前缀长度 \(\ge 2\)，设这个最长公共前缀为 \(aA\)，其中 \(a\) 是单个字符，\(A\) 是一个非空字符串。

那么设后缀 sa[rk[i-1]-1] 为 \(aAB\)，i-1 为 \(aAC\)，则 \(B \lt C\)，且后缀 sa[rk[i-1]-1]+1 为 \(AB\)，i 为 \(AC\)。

后缀 sa[rk[i]-1] 因为只比 i 前一名，所以是小于 i 中最大的，又因为 \(AB \lt AC\)，所以 \(AB \le\) 后缀 sa[rk[i]-1] \(\lt AC\)，容易看出后缀 i 和后缀 sa[rk[i]-1] 有公共前缀 \(A\)。

于是 ht[rk[i]] $\ge |A| = $ ht[rk[i-1]]-1。

\(\square\)

由此，我们从 ht[rk[i-1]]-1 开始暴力拓展 ht[rk[i]]，在 \(\mathrm O(n)\) 的时间复杂度内得到 ht。

ht 数组有这样一个性质：后缀 i,j 的最长公共前缀长度等于 ht[rk[i],rk[j]) 中的最小值。（钦定 rk[i] \(\lt\) rk[j]）

因此我们可以用 ST 表 \(\mathrm O(n \log n)\) 预处理后 \(\mathrm O(1)\) 询问任意后缀的最长公共前缀长度。

例题

UOJ 35.后缀排序 
 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5;
int n,sa[N + 2],cnt[N + 2],rk[2][N + 2],ht[N + 2];
char s[N + 2];
struct node {
    int x,y,id;
} p[N + 2],q[N + 2];
bool operator<(const node& a,const node& b) {
    return a.x!=b.x?a.x<b.x:a.y<b.y;
}
bool operator==(const node& a,const node& b) {
    return a.x==b.x&&a.y==b.y;
}
void Sort() {
    memset(cnt,0,sizeof(*cnt)*(n+1));
    for(int i=1; i<=n; ++i) ++cnt[p[i].y];
    for(int i=1; i<=n; ++i) cnt[i]+=cnt[i-1];
    for(int i=n; i>=1; --i) q[cnt[p[i].y]--]=p[i];
    memset(cnt,0,sizeof(*cnt)*(n+1));
    for(int i=1; i<=n; ++i) ++cnt[q[i].x];
    for(int i=1; i<=n; ++i) cnt[i]+=cnt[i-1];
    for(int i=n; i>=1; --i) p[cnt[q[i].x]--]=q[i];
}
int main() {
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1; i<=n; ++i) cnt[s[i]]=1;
    for(int i=1; i<128; ++i) cnt[i]+=cnt[i-1];
    for(int i=1; i<=n; ++i) rk[0][i]=cnt[s[i]];
    for(int j=1,k=1; j<=n; j<<=1,k^=1) {
        for(int i=1; i<=n; ++i) p[i]={rk[k^1][i],i+j<=n?rk[k^1][i+j]:0,i};
        Sort();
        for(int i=1,t=0; i<=n; ++i)
            if(i>1&&p[i]==p[i-1])
                rk[k][p[i].id]=t;
            else
                rk[k][p[i].id]=++t;
        if((j<<1)>n) swap(rk[k],rk[0]);
    }
    for(int i=1; i<=n; ++i) sa[rk[0][i]]=i;
    for(int i=1; i<=n; ++i) printf("%d ",sa[i]);
    putchar('\n');
    for(int i=1; i<=n; ++i) {
        if(rk[0][i]==1) continue;
        int k=i>1?max(0,ht[rk[0][i-1]]-1):0;
        while(i+k<=n&&sa[rk[0][i]-1]+k<=n&&s[i+k]==s[sa[rk[0][i]-1]+k]) ++k;
        ht[rk[0][i]]=k;
    }
    for(int i=2; i<=n; ++i) printf("%d ",ht[i]);
    return 0;
}