ABC362 G問題（解説記事）で suffix array を紹介しました。これを効率よく構成するアルゴリズムを紹介します。
Suffix array
Suffix array（接尾辞配列）とは、与えられた文字列 $S$ に対して、すべての接尾辞を辞書順にソートしたものです。配列には、接尾辞そのものではなく、接尾辞の開始位置を格納します。
Suffix array を構成すると、文字列の検索が効率的に行えます。ABC362 G問題自体がその例となっています。
素朴な実装
最初に素朴な実装を紹介します。部分文字列とインデックスの pair を sort します。このインデックスを suffix array として返します。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> suffix_array(string s)
{
int n = s.length();
vector<int> result(n);
vector<pair<string, int>> buffer(n);
for (int i = 0; i < n; ++i) {
buffer[i] = make_pair(s.substr(i), i);
}
sort(buffer.begin(), buffer.end());
for (int i = 0; i < n; ++i) {
result[i] = buffer[i].second;
}
return result;
}
int main()
{
string s;
cin >> s;
vector<int> sa = suffix_array(s);
for (int i = 0; i < sa.size(); ++i) {
cout.width(4);
cout << sa[i] << ":" << s.substr(sa[i]) << endl;
}
return 0;
}例として、”abracadabra” という文字をよく使います。この入力に対して、プログラムの出力は以下となります。
$ ./suffix_array_sort.exe
abracadabra
10:a
7:abra
0:abracadabra
3:acadabra
5:adabra
8:bra
1:bracadabra
4:cadabra
6:dabra
9:ra
2:racadabra実践的な suffix array 実装
素朴な実装は、長さ $N$ の文字列のソートに $N \log N$ の計算量が必要なため、合わせた計算量は、$N^2 \log N$ となります。
Manber & Myers が考案した、ダブリングを使った計算量 $N \log^2 N$ のプログラムを紹介します。最初は1文字分だけでソートして、次に2文字分、4文字分とソートで比較する範囲を倍々に増やしていきます。比較する文字数は、配列 r で管理します。
この実装は「蟻本」（「プログラミングコンテストチャレンジブック」第2版 秋葉拓哉、岩田陽一、北川宣稔著、マイナビ 2012年）を参考にしました。このため、Vector コンテナではなく配列を対象としました。コードは以下となります。
参考までに、AtCoder Library の suffix array 構築は、SA-ISという線形時間で処理するアルゴリズムが採用されていました。
#define MAX_N 500000
int n, k;
int r[MAX_N + 1];
int t[MAX_N + 1];
int sa[MAX_N + 1];
bool compare_sa(int i, int j)
{
if (r[i] != r[j]) {
return r[i] < r[j];
} else {
int ri;
if (i + k < n) {
ri = r[i + k];
} else {
ri = -1;
}
int rj;
if (j + k < n) {
rj = r[j + k];
} else {
rj = -1;
}
return ri < rj;
}
}
void suffix_array(string s, int *sa)
{
n = s.length();
for (int i = 0; i < n; ++i) {
sa[i] = i;
r[i] = s[i];
}
for (k = 1; k < n; k *= 2) {
sort(sa, sa + n, compare_sa);
t[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
t[sa[i]] = t[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for (int i = 0; i < n; ++i) {
r[i] = t[i];
}
}
}ライブラリのテスト
Library Checker でアルゴリズムをテストします。以下がアルゴリズムのリンク先です。
テストしたプログラムは以下です。AC（Accepted）と判定されました。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define MAX_N 500000
int n, k;
int r[MAX_N + 1];
int t[MAX_N + 1];
int sa[MAX_N + 1];
bool compare_sa(int i, int j)
{
if (r[i] != r[j]) {
return r[i] < r[j];
} else {
int ri;
if (i + k < n) {
ri = r[i + k];
} else {
ri = -1;
}
int rj;
if (j + k < n) {
rj = r[j + k];
} else {
rj = -1;
}
return ri < rj;
}
}
void suffix_array(string s, int *sa)
{
n = s.length();
for (int i = 0; i < n; ++i) {
sa[i] = i;
r[i] = s[i];
}
for (k = 1; k < n; k *= 2) {
sort(sa, sa + n, compare_sa);
t[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
t[sa[i]] = t[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for (int i = 0; i < n; ++i) {
r[i] = t[i];
}
}
}
int main()
{
string s;
cin >> s;
suffix_array(s, sa);
for (int i = 0; i < n; ++i) {
cout << sa[i] << " \n"[i == n - 1];
}
return 0;
}最後に
Suffix array について整理しました。
