接尾辞配列 (Suffix Array)¶

SA :
LCP :
SA^-1 :

定義¶

文字列wの接尾辞を，辞書式順序に並べ直したときの，接尾辞番号を配列として保存したもの．

構築アルゴリズム¶

素朴な手法 /Scripts/Python/SA.py

LarssonSadakane法

#include <vector>
#include <string>
#include <algorithm>


// LarssonSadakane(Doubling Technique & Multi-Key QuickSortもどき)
// 本家論文ではternary-splitで内側のソートを行うが
// 以下の実装では一段ですべてsplitしている
namespace LarssonSadakane{
	struct Cmp{
		int h;
		const vector<int> &rank;
		Cmp(vector<int> &rank):h(0),rank(rank){}
		bool operator()(int a,int b){
			return a==b ? false : rank[a]!=rank[b] ? rank[a]<rank[b] : rank[a+h]<rank[b+h];
		}
	};
	vector<int> SuffixArray(const string &str){
		int n = str.size(),m = 0;						// 文字列長、区間長
		vector<int> sa(n+1,n),rank(n+1,0),order(n+1,0),interval(n+2,0);		// 接尾辞配列、比較用配列、h-order、ソートされている区間
		for(int i=0 ; i<n ; i++)sa[i] = i,rank[i] = str[i];			// 始めの比較用の値を代入 
		for (Cmp cmp(rank) ; order[n]!=n ; cmp.h?cmp.h<<=1:cmp.h++) {		// 比較位置を倍に
			interval[++m]=n+1;						// 区間の最後を文字列長に
			for(int i=0 ; m>0 ; i++,m--)					// h-orderでソート
				sort(sa.begin()+interval[i],sa.begin()+interval[i+1],cmp);
			for(int i=0 ; i<n ; i++){					// h-orderと次のシンボルごとの区間を求める
				order[i+1] = order[i];							
				if(cmp(sa[i],sa[i+1]))order[i+1]++,interval[++m]=i+1;
			}
			for(int i=0 ; i<=n ; i++)rank[sa[i]] = order[i];		// 求めたh-orderを比較用の配列に代入
		}
		return sa;
	}
};

参考文献¶

N.J.Larsson and K.Sadakane. Faster suffix sorting. Technical report LU-CSTR:99-214, Dept. of Computer Science, Lund University, Sweden, 1999.