山姆的競程日記

從綠牌開始的旅途

0%

Suffix Array 後綴數組

發表於 更新於 Disqus：

因為看到電神「雞塊」在「雞塊的競程隨筆」介紹了Suffix Array

今天上Codeforces的EDU學了Suffix Array

覺得Suffix Array真的是一個還滿神奇的東西的

因此決定來紀錄一下怎麼找Suffix Array以及其用途

什麼是Suffix Array

Suffix Array在維基百科上面被稱為「後綴數組」

不過他的寫法我看不太懂(´_ゝ`)

總而言之，假設我們有一字串，就叫他aabbaa好了

我們找出這個字串的所有後綴並列出來 （數字為字串從第幾個字元開始的後綴字串）

1
2
3
4
5
6
7
0 aabbaa
1 abbaa
2 bbaa
3 baa
4 aa
5 a
6

有這六個 而我們將他們以字典序去做排列 會得到下面這個
1
2
3
4
5
6
7
6
5 a
4 aa
0 aabbaa
1 abbaa
3 baa
2 bbaa

而 $\text{6 5 4 0 1 3 2}$ 就是我們要找的Suffix Array

他的用途我們會在這篇文章後面提到

如何找到Suffix Array (Naive Solution)

如果要做到這件事 你應該會覺得很簡單

因為我們需要做的就只是把所有後綴給找出來存在陣列中

並用各種排序法或語言內建的sort去排序

例如：

1
2
3
4
5
6
7
8
9
10
11
string s;
cin >> s;
int n = s.size();
vector<pair<string,int>> v;
string tmp = "";
for(int i = n-1;i >= -1;i--){
	v.push_back({tmp,i+1});
	if(i!=-1)tmp = s[i] + tmp;
}
sort(v.begin(),v.end());
for(auto p : v) cout << p.second << " " << p.first << "\n";

結果會是
1
2
3
4
5
6
7
8
aabbaa
6 
5 a
4 aa
0 aabbaa
1 abbaa
3 baa
2 bbaa

不過讓我們來分析一下 （用 $n$ 表示字串長度)

所有後綴的字串長度會是 $n,(n-1),(n-2),(n-3),…,2,1$

全部相加起來則會是 $\frac{n(n+1)}{2}$ 的空間

當 $n$ 的值大到 $10^4,10^5,10^6$ 的時候 空間複雜度就會爆掉

然後再加上排序的複雜度也是不太理想 $O(nlogn \times |s|)$

總共複雜度會達到 $O(n^2logn)$

改進找到Suffix Array的方式

由於上面的方式實在是非常沒有效率又佔空間

如果我們只紀錄Suffix Array的數值 我們所需要的空間複雜度則為 $O(n)$

為了方便起見 我們在字串後面加上 「\$」 （\$的字典序小於所有字母）

並把字串讓字串形成環 字串長度也加到 $2^k$

1
2
3
4
5
6
7
8
9
aabbaa$
0 aabbaa$a
1 abbaa$aa
2 bbaa$aab
3 baa$aabb
4 aa$aabba
5 a$aabbaa
6 $aabbaa$
  01234567 => 字串長度:2^3 => 8

排序之後則變成

1
2
3
4
5
6
7
8
aabbaa$
6 $aabbaa$
5 a$aabbaa
4 aa$aabba
0 aabbaa$a
1 abbaa$aa
3 baa$aabb
2 bbaa$aab

我們如何去排序Suffix Array呢？

我們先分別找到 $k=0, k=1, k=2,…$ 時的排序

我們可以用 $k=0$ 去推出 $k=1$ 的狀況

我們先找出每個後綴字串的前 $2^k$ 個字元

1
2
3
4
5
6
7
8
9
10
k=0        k=1         k=2

aabbaa$    aabbaa$     aabbaa$
0 a        0 aa        0 aabb
1 a        1 ab        1 abba
2 b        2 bb        2 bbaa
3 b        3 ba        3 baa$
4 a        4 aa        4 aa$a
5 a        5 a$        5 a$aa
6 $        6 $a        6 $aab

進行排序之後會得到

1
2
3
4
5
6
7
8
9
k=0        k=1         k=2
aabbaa$    aabbaa$     aabbaa$
6 $        6 $a        6 $aabb
0 a        5 a$        5 a$aa
1 a        0 aa        4 aa$a
4 a        4 aa        0 aabb
5 a        1 ab        1 abba
2 b        3 ba        3 baa$
3 b        2 bb        2 bbaa

如何使用 $k=0$ 的 Suffix Array 去得到 $k=1$ 的值呢？

我們先挑出 $k=0$ 來觀察 並把字元的Rank寫上去(離散化)

1
2
3
4
5
6
7
8
9
k=0      
aabbaa$ Rank
6 $      0
0 a      1
1 a      1
4 a      1
5 a      1
2 b      2
3 b      2

有了Rank的值之後 我們就可以用他來得到 $k=1$ 時的數值了

用這個方式去排序就可以得到答案了
1
2
3
4
5
6
7
8
9
k=1                               k=1
aabbaa$    對應Rank                aabbaa$    對應Rank
6 $a        0 1                   6 $a        0 1
0 aa        1 1                   5 a$        1 0
1 ab        1 2         排序Rank   0 aa        1 1
4 aa        1 1         =======>  4 aa        1 1
5 a$        1 0                   1 ab        1 2
2 bb        2 2                   3 ba        2 1
3 ba        2 1                   2 bb        2 2

之後再去用上面的資料得到新的Rank與Suffix Array

我們就可以再用其去求得 $k=2,k=3,…$ 的值了

時間複雜度: $O(nlogn+nlogn \times logn) = O(nlog^2n)$

（一開始的 $nlogn$ 為排序單個字元， 後面的 $nlogn$ 為排序pair，而我們會做 $logn$ 次

目前的程式碼

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
string s;
cin >> s;
s += '$';
int n = s.size();
int pos[n], rank[n];
{
    //k = 0
    //tmp的作用為暫存我們之後要排序的東西
    vector<pair<char,int>> tmp(n);
    for(int i = 0;i < n;i++) tmp[i] = {s[i],i};
    sort(tmp.begin(),tmp.end());
    for(int i = 0;i < n;i++) pos[i] = v[i].second;
    rank[pos[0]] = 0;
    for(int i = 1;i < n;i++){
        if(tmp[i].first == tmp[i-1].first) rank[pos[i]] = rank[pos[i-1]];
        else rank[pos[i]] = rank[pos[i-1]] + 1;
    }
}
int k = 0;
while(1<<k <= n){
    //tmp的作用為暫存我們之後要排序的東西
    vector<pair<pair<int,int>,int>> tmp(n);
    for(int i = 0;i < n;i++) v[i] = {{rank[i],rank[(i+(1<<k))%n]},i};
    sort(tmp.begin(),tmp.end());
    for(int i = 0;i < n;i++) pos[i] = tmp[i].second;
    rank[pos[0]] = 0;
    for(int i = 1;i < n;i++){
        if(tmp[i].first == tmp[i-1].first) rank[pos[i]] = rank[pos[i-1]];
        else rank[pos[i]] = rank[pos[i-1]] + 1;
    }
    k++;
}
for(auto x : pos) cout << x << " ";

更進一步的改善複雜度

一般來說 排序所使用的複雜度為 $O(nlogn)$

但是幾種排序能做到線性的排序

比較常見的為Radix Sort及Counting Sort

在這裡不細講這兩種排序如何達成 直接丟一張維基百科上面的說明

Counting Sort:

Radix Sort則是對每一位都去進行Counting Sort

複雜度:

Counting Sort: $O(n+k)$ ($k$ 為陣列的範圍)

Radix Sort: $O(d\times(n+k))$ ($d$ 為幾位數字)

而我們這裡就可以將原本排序pair的 $O(nlogn \times logn)$

用這兩種排序變為 $O(n\times logn)$

因此求Suffix Array的複雜度降低為 $O(nlogn+nlogn)=O(nlogn)$

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
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void count_sort(vector<int> &pos, vector<int> &rank){
	int n = pos.size();
	vector<vector<int>> cnt(n);
	for(int i : pos) cnt[rank[i]].push_back(i);
	for(int i = 0, idx = 0;i < n;i++)
		for(auto x : cnt[i])
			pos[idx++] = x;
}

void get_suffix(string s, vector<int> &pos){
	s += '$';
	int n = s.size();
	vector<int> rank(n);
	//k = 0
	iota(pos.begin(),pos.end(),0);
	sort(pos.begin(),pos.end(),[&](int a, int b){ return s[a] < s[b]; });
	for(int i = 0;i < n;i++){
		if(i==0){ 
			rank[pos[i]] = 0;
		}else{
			rank[pos[i]] = rank[pos[i-1]] + (s[pos[i]]!=s[pos[i-1]]);
		}
	}
	//k > 0
	vector<int> new_rank(n);
	for(int k = 0;(1<<k) <= n;k++){
		for(int i = 0;i < n;i++)
			pos[i] = (pos[i] - (1<<k)%n + n ) % n;
		count_sort(pos,rank);
		new_rank[pos[0]] = 0;
		for(int i = 1;i < n;i++){
			pair<int,int> prev = {rank[pos[i-1]], rank[(pos[i-1]+(1<<k))%n]};
			pair<int,int> now = {rank[pos[i]], rank[(pos[i]+(1<<k))%n]};
			new_rank[pos[i]] = new_rank[pos[i-1]] + (prev!=now);
		}
		rank = new_rank;
	}
}

signed main(){
	fastio
	string s;
	cin >> s;
	vector<int> ans(s.size()+1);
	get_suffix(s,ans);
	for(auto x : ans) cout << x << " " << s.substr(x) << "\n";
}

用途

接下來，了解如何找到一個字串的Suffix Array之後，最重要的就是他能用在哪裡了

一、得知一個字串是否為這個字串的子字串(SubString)

Codeforces 題目連結

如何做到這件事情呢

首先我們要知道，一個字串的子字串(SubString)一定是一個字串後綴(Suffix)的前綴(Prefix)

聽起來很難懂 不過來舉例 同樣是aabbaa這個字串 我們要找bb這個子字串

1
2
3
4
5
6
7
8
aabbaa 
6 
5 a
4 aa
0 aabbaa
1 abbaa
3 baa
2 *bb*aa

我們可以看到，在bbaa這個子字串的前綴出現了bb這個子字串

除了知道字串是否為這個字串的子字串 我們也可以知道他出現的位置在 $index = 2$ 的位置


那如何去尋找這個子字串呢 我們可以利用「二分搜」來找到出現他的位置

由於Suffix Array已經將字串排序好了 所以二分搜可以直接使用

時間複雜度: $O(nlogn)$

二、子字串(Substring)在字串中出現了幾次(Occurence)

Codeforces 題目連結

總之這個跟剛剛的概念是一樣的 只是二分搜時稍微改變一下寫法

這裡就不附程式碼了

複雜度依舊為 $O(nlogn)$

三、最長共同前綴 Longest Common Prefix（LCP Array)

接下來的用途需要這個才有辦法繼續講

是一個非常重要的一個東西

首先，我們有了 Suffix Array 這個陣列
我們去找 Suffix Array 的 LCP 並弄成陣列 我們稱其為 LCP Array

範例：（一樣拿前面的aabbaa來做示範)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
aabbaa
6 
    =>共同前綴為"" 長度:0
5 a
    =>共同前綴為"a" 長度:1
4 aa
    =>共同前綴為"aa" 長度:2
0 aabbaa
    =>共同前綴為"a" 長度:1
1 abbaa
    =>共同前綴為"" 長度:0
3 baa
    =>共同前綴為"b" 長度:1
2 bbaa

因此 這個字串的 LCP Array 為 $\text{0 1 2 1 0 1}$

而如果我們是希望能求第 $i$ 個前綴與第 $j$ 個前綴的LCP呢？

那麼 $LCP(i,j)$則為 $min(LCP(a[i],a[i]+1),LCP(a[i]+1,a[i]+2),…)$
（Suffix Array 用 $a[]$ 來表示）

我們可以利用「線段樹(Segment Tree)」或「稀疏表(Sparse Table)」來求得RMQ

而這裡的重點是：我們要如何得到 LCP Array 呢？
同樣以 aabbaa 這個陣列來舉例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
aabbaa
6 
    =>共同前綴為"" 長度:0
5 a
    =>共同前綴為"a" 長度:1
4 aa
    =>共同前綴為"aa" 長度:2
0 aabbaa
    =>共同前綴為"a" 長度:1
1 abbaa
    =>共同前綴為"" 長度:0
3 baa
    =>共同前綴為"b" 長度:1
2 bbaa

先找 $0$ 與其 Suffix Array的前一個位置 $4$ 的 LCP

我們可以知道其值為 $2$

知道這個 $2$ 值之後 我們可以知道 當要掃 $1$ 和 $5$ 的 LCP 時

他們的第一個字元一定相等($2-1$) 因此 我們只需要掃 $1$ 以後的字元去得到LCP

以此類推 我們將可以得到LCP的答案

經過分析之後 我們可以知道有 Suffix Array 後要求 LCP Array 所需的時間複雜度為 $O(n)$

由於原本求 Suffix Array 時的時間複雜度為 $O(nlogn)$

因此總共時間複雜度為 $O(nlogn)$

Codeforces 題目連結

四、一個陣列中共有幾個子字串(Substring)

Codeforces 題目連結

如何求一個字串總共有幾個子字串呢 我們可以利用剛剛求得的LCP Array來幫助求解

我們可以想到 一個字串的後綴(Suffix)長度 代表有幾個前綴(Prefix)

扣掉LCP(重複算的Prefix) 則為我們要的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
aabbaa
6 
    =>共同前綴為"" 長度:0 =>　子字串數量：(6-5)-0 = 1
5 a
    =>共同前綴為"a" 長度:1 => 子字串數量: (6-4)-1 = 1
4 aa
    =>共同前綴為"aa" 長度:2 => 子字串數量: (6-0)-2 = 4
0 aabbaa
    =>共同前綴為"a" 長度:1 => 子字串數量: (6-1)-1 = 4
1 abbaa
    =>共同前綴為"" 長度:0 => 子字串數量: (6-3)-0 = 3
3 baa
    =>共同前綴為"b" 長度:1 => 子字串數量: (6-2)-1 = 3
2 bbaa                                 Total: 16

經由上面的操作 我們能在有LCP Array後 在 $O(n)$ 時間求出子字串數量

五、最長共同子字串 Longest Common Substring

這題應該是大部分人在學到 dp 時都會解到的經典題目

而使用 dp 解這題時 一般的複雜度會是 $O(n^2)$

而當我們有了 Suffix Array 與 LCP Array 之後

我們就可以用 $O(nlogn)$ 的複雜度求得最長共同子字串了


如何用 Suffix Array 找到最長共同子字串呢

我們可以先將兩個字串接在一起 然後去找他們的 Suffix Array 與 LCP

範例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
aabbcc#dabc //為了方便解釋 我們在字串中間加入一個# (#的字典序比字母小）
6 #dabc$
11 $
-------------------------------- 我們可以無視上面那兩個suffix
0 aabbcc#dabc$
                =>共同前綴為"a"  長度:1
1 abbcc#dabc$
                =>共同前綴為"ab" 長度:2
8 abc$
                =>共同前綴為""   長度:0
2 bbcc#dabc$
                =>共同前綴為"b"  長度:1
9 bc$
                =>共同前綴為"bc" 長度:2
3 bcc#dabc$
                =>共同前綴為""   長度:0
5 c#dabc$
                =>共同前綴為"c"  長度:1
10 c$
                =>共同前綴為"c"  長度:1
4 cc#dabc$
                =>共同前綴為""   長度:0
7 dabc$

從這些東西 我們可以知道的是如果後綴是從 $index=6$ 以後開始的

那他的前綴會是第二個字串的子字串（亦即沒出現#符號的）
我們可以給這些字串做上 $1$ 和 $2$ 的標記

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
0 aabbcc#dabc$  編號:1
                =>共同前綴為"a"  長度:1
1 abbcc#dabc$   編號:1
                =>共同前綴為"ab" 長度:2
8 abc$          編號:2
                =>共同前綴為""   長度:0
2 bbcc#dabc$    編號:1
                =>共同前綴為"b"  長度:1
9 bc$           編號:2
                =>共同前綴為"bc" 長度:2
3 bcc#dabc$     編號:1
                =>共同前綴為""   長度:0
5 c#dabc$       編號:1
                =>共同前綴為"c"  長度:1
10 c$           編號:2
                =>共同前綴為"c"  長度:1
4 cc#dabc$      編號:1
                =>共同前綴為""   長度:0
7 dabc$         編號:2

而要求得兩字串的最長子字串 就會是所有編號為 $1$ 和 $2$ 字串 LCP 的最大值

複雜度:$O(nlogn)$

六、多個字串的共同子字串 (TIOJ 2151)

與兩個字串的作法基本上一樣

不過這題求出的子字串還不能重複

而且要注意Counting Sort用vector會TLE

更多應用代補

代補

心得

Suffix Array 真的是一個很神奇的東西 可以把一些平常認為需要 $O(n^2)$ 的題目

利用 Suffix Array 與 LCP Array 在 $O(nlogn)$ 解出來

這篇文章今後在解到更多Suffix Array的題目之後 會再更新