Suffix Array (SA-IS) (string/suffix_array.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-03 22:00:44+09:00

なにこれ

文字列の Suffix Array を構築する．

コンストラクタ

• SuffixArray(s)

メンバ関数

• get_array()：文字列 s の Suffix Array を構築する．

計算量

文字列 s の長さを $n$ とする．

• コンストラクタ：$O(n)$
• get_array()：$O(n)$

補足

SA-IS の処理の流れ

Open

1. 文字列 $s$ の末尾に辞書順で最も小さい文字を追加する．文字列 $s$ の長さを $n$ とする．
2. $i = n-1, ..., 1, 0$ の順に L-type、S-type のいずれであるかを決定する．
   1. $i = n-1$ ならば S-type．
   2. $s_i < s_{i+1}$ ならば S-type．
   3. $s_i > s_{i+1}$ ならば L-type．
   4. $s_i = s_{i+1}$ ならば $i+1$ の type と同じ．
3. $i\ (< n)$ に対して LMS であるかを決定する．
   • $i$ が S-type かつ $i-1$ が L-type のとき $i$ は LMS．
4. Induced Sorting を行う．
   1. 仮の Suffix Array $A$ を作成し，各 suffix の頭文字を基準にバケットの区切りを決定する．
   2. LMS を対応するバケットに下から埋める．
   3. $j = 0, 1, ..., n-1$ の順に次の処理を行う．
      • $A_j$ が埋まっており，かつ $i = A_j - 1$ が L-type ならば対応するバケットに上から埋める．
   4. $j = n-1, ..., 1, 0$ の順に次の処理を行う．
      • $i = A_j - 1$ が S-type ならば対応するバケットに下から埋める．ただし，初めにバケットに埋めた LMS は上書きして埋める．
5. LMS である $i$ に対して LMS-string $t_i$ を次のように定義する．
   • $i = n-1$ ならば，$t_i = s[n-1:n-1]$
   • $i \neq n-1$ ならば，$i$ の次の LMS を $j$ として $t_i = s[i:j]$
   • (性質) LMS-string は $A$ の上で既にソートされている．
6. LMS である $i$ に対して連番を振り，文字列 $s$ 上で現れる順番にソートした配列を $s'$ とする．ただし，重複する LMS-string には同じ番号を振る．
7. LMS-string に重複があるならば，$s'$ に対して SA-IS を行う．
   • これにより LMS $i$ に対する接尾辞 $s[i:]$ を基準に $i$ をソートすることができる．重複がないならば既にソートされている．
8. Induced Sorting を行う．ただし，初めに埋める LMS は上から前項でソートした順に埋まるようにする．
9. 構築された Suffix Array $A$ から末尾を取り除く．

参考

• 接尾辞配列(Suffix Array) - Shogo Computing Laboratory

Verified with

• test/aoj_ALDS1_14_D.cpp
• test/yosupo_suffixarray.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct SuffixArray {
private:
	int N;
	vector<int> si;

public:
	SuffixArray(const string &s) : N(s.size()), si(s.size() + 1) {
		for(int i = 0; i < N; i++) si[i] = s[i];
		si[N] = 0;
	}

private:
	vector<int> induced_sort(const vector<int> &s,
							 const vector<int> &lms_idx,
							 const vector<bool> &ls,
							 const int c_max) {
		const int n = s.size();
		vector<int> c_num(c_max + 1, 0), bucket_top(c_max + 1, 0), bucket_now(c_max + 1);
		for(int c : s) c_num[c]++;
		for(int i = 0; i < c_max; i++) {
			bucket_top[i + 1] = bucket_top[i] + c_num[i];
			bucket_now[i] = bucket_top[i + 1] - 1;
		}
		bucket_now[c_max] = n - 1;

		vector<int> pseudo_sa(n, -1);
		for(int idx : lms_idx) {
			pseudo_sa[bucket_now[s[idx]]--] = idx;
		}

		for(int i = 0; i <= c_max; i++) bucket_now[i] = bucket_top[i];
		for(int i = 0; i < n; i++) {
			if(pseudo_sa[i] <= 0) continue;
			int idx = pseudo_sa[i] - 1;
			if(ls[idx]) continue;
			pseudo_sa[bucket_now[s[idx]]++] = idx;
		}

		for(int i = 0; i < c_max; i++) bucket_now[i] = bucket_top[i + 1] - 1;
		bucket_now[c_max] = n - 1;
		for(int i = n - 1; i >= 0; i--) {
			if(pseudo_sa[i] == 0) continue;
			int idx = pseudo_sa[i] - 1;
			if(not ls[idx]) continue;
			pseudo_sa[bucket_now[s[idx]]--] = idx;
		}

		return pseudo_sa;
	}

	bool same_lms_strings(const vector<int> &s, const vector<bool> &lms, int idx1, int idx2) {
		if(s[idx1++] != s[idx2++]) return false;
		if(max(idx1, idx2) >= lms.size()) return false;
		while(1) {
			if(s[idx1] != s[idx2]) return false;
			if(lms[idx1] and lms[idx2]) return true;
			if(lms[idx1] != lms[idx2]) return false;
			idx1++, idx2++;
		}
	}

	vector<int> sa_is(const vector<int> &s, const int c_max = 127) {
		int n = s.size();
		vector<bool> ls(n, false), lms(n, false);
		vector<int> lms_idx;

		ls[n - 1] = true;

		for(int i = n - 2; i >= 0; i--) {
			if(s[i] < s[i + 1]) {
				ls[i] = true;
			}
			else if(s[i] == s[i + 1]) {
				ls[i] = ls[i + 1];
			}
			else if(ls[i + 1]) {
				lms[i + 1] = true;
				lms_idx.emplace_back(i + 1);
			}
		}

		reverse(lms_idx.begin(), lms_idx.end());
		vector<int> sa = induced_sort(s, lms_idx, ls, c_max);

		vector<int> lms_str_c(n, -1);
		lms_str_c[sa[0]] = 1;
		int counter = 1;
		int prev_lms = 0;
		for(int i = 1; i < n; i++) {
			if(not lms[sa[i]]) continue;
			if(same_lms_strings(s, lms, prev_lms, sa[i])) {
				lms_str_c[sa[i]] = counter;
			}
			else {
				lms_str_c[sa[i]] = ++counter;
			}
			prev_lms = sa[i];
		}

		int lms_n = lms_idx.size();
		vector<int> new_lms_idx(lms_n);
		if(counter == lms_idx.size()) {
			new_lms_idx[0] = sa[0];
			for(int i = n - 1, j = 1; j < lms_n; i--) {
				if(lms[sa[i]]) new_lms_idx[j++] = sa[i];
			}
		}
		else {
			vector<int> new_s(lms_n + 1);
			for(int i = 0; i < lms_n; i++) {
				new_s[i] = lms_str_c[lms_idx[i]];
			}
			new_s[lms_n] = 0;

			vector<int> lms_idx_order = sa_is(new_s, counter);
			lms_idx_order.erase(lms_idx_order.begin());
			for(int i = 0; i < lms_n; i++) new_lms_idx[lms_n - 1 - i] = lms_idx[lms_idx_order[i]];
		}

		return induced_sort(s, new_lms_idx, ls, c_max);
	}

public:
	vector<int> get_array() {
		vector<int> sa = sa_is(si);
		sa.erase(sa.begin());
		return sa;
	}
};

#line 2 "string/suffix_array.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

struct SuffixArray {
private:
	int N;
	vector<int> si;

public:
	SuffixArray(const string &s) : N(s.size()), si(s.size() + 1) {
		for(int i = 0; i < N; i++) si[i] = s[i];
		si[N] = 0;
	}

private:
	vector<int> induced_sort(const vector<int> &s,
							 const vector<int> &lms_idx,
							 const vector<bool> &ls,
							 const int c_max) {
		const int n = s.size();
		vector<int> c_num(c_max + 1, 0), bucket_top(c_max + 1, 0), bucket_now(c_max + 1);
		for(int c : s) c_num[c]++;
		for(int i = 0; i < c_max; i++) {
			bucket_top[i + 1] = bucket_top[i] + c_num[i];
			bucket_now[i] = bucket_top[i + 1] - 1;
		}
		bucket_now[c_max] = n - 1;

		vector<int> pseudo_sa(n, -1);
		for(int idx : lms_idx) {
			pseudo_sa[bucket_now[s[idx]]--] = idx;
		}

		for(int i = 0; i <= c_max; i++) bucket_now[i] = bucket_top[i];
		for(int i = 0; i < n; i++) {
			if(pseudo_sa[i] <= 0) continue;
			int idx = pseudo_sa[i] - 1;
			if(ls[idx]) continue;
			pseudo_sa[bucket_now[s[idx]]++] = idx;
		}

		for(int i = 0; i < c_max; i++) bucket_now[i] = bucket_top[i + 1] - 1;
		bucket_now[c_max] = n - 1;
		for(int i = n - 1; i >= 0; i--) {
			if(pseudo_sa[i] == 0) continue;
			int idx = pseudo_sa[i] - 1;
			if(not ls[idx]) continue;
			pseudo_sa[bucket_now[s[idx]]--] = idx;
		}

		return pseudo_sa;
	}

	bool same_lms_strings(const vector<int> &s, const vector<bool> &lms, int idx1, int idx2) {
		if(s[idx1++] != s[idx2++]) return false;
		if(max(idx1, idx2) >= lms.size()) return false;
		while(1) {
			if(s[idx1] != s[idx2]) return false;
			if(lms[idx1] and lms[idx2]) return true;
			if(lms[idx1] != lms[idx2]) return false;
			idx1++, idx2++;
		}
	}

	vector<int> sa_is(const vector<int> &s, const int c_max = 127) {
		int n = s.size();
		vector<bool> ls(n, false), lms(n, false);
		vector<int> lms_idx;

		ls[n - 1] = true;

		for(int i = n - 2; i >= 0; i--) {
			if(s[i] < s[i + 1]) {
				ls[i] = true;
			}
			else if(s[i] == s[i + 1]) {
				ls[i] = ls[i + 1];
			}
			else if(ls[i + 1]) {
				lms[i + 1] = true;
				lms_idx.emplace_back(i + 1);
			}
		}

		reverse(lms_idx.begin(), lms_idx.end());
		vector<int> sa = induced_sort(s, lms_idx, ls, c_max);

		vector<int> lms_str_c(n, -1);
		lms_str_c[sa[0]] = 1;
		int counter = 1;
		int prev_lms = 0;
		for(int i = 1; i < n; i++) {
			if(not lms[sa[i]]) continue;
			if(same_lms_strings(s, lms, prev_lms, sa[i])) {
				lms_str_c[sa[i]] = counter;
			}
			else {
				lms_str_c[sa[i]] = ++counter;
			}
			prev_lms = sa[i];
		}

		int lms_n = lms_idx.size();
		vector<int> new_lms_idx(lms_n);
		if(counter == lms_idx.size()) {
			new_lms_idx[0] = sa[0];
			for(int i = n - 1, j = 1; j < lms_n; i--) {
				if(lms[sa[i]]) new_lms_idx[j++] = sa[i];
			}
		}
		else {
			vector<int> new_s(lms_n + 1);
			for(int i = 0; i < lms_n; i++) {
				new_s[i] = lms_str_c[lms_idx[i]];
			}
			new_s[lms_n] = 0;

			vector<int> lms_idx_order = sa_is(new_s, counter);
			lms_idx_order.erase(lms_idx_order.begin());
			for(int i = 0; i < lms_n; i++) new_lms_idx[lms_n - 1 - i] = lms_idx[lms_idx_order[i]];
		}

		return induced_sort(s, new_lms_idx, ls, c_max);
	}

public:
	vector<int> get_array() {
		vector<int> sa = sa_is(si);
		sa.erase(sa.begin());
		return sa;
	}
};

Back to top page