Artifact 24b4786c5875bcf17e6190dc9d122a18b12f0c95

• File lib/dataStructure/suffixArray.cpp
  • 2012-07-22 18:00:41 - part of checkin [cd0467fefc] on branch trunk - Suffix Array. (user: kinaba) [annotate]

//-------------------------------------------------------------
// Suffix Array
//   O(N log N) construction by Larsson-Sadakane
//    from http://www.prefield.com/algorithm/string/suffix_array.html
//
// compute_suffix_array("baca")
//   = {"aca" < "a$" < "baca" < "ca"} = {1,3,0,2}
//   EOS is set to be the largest symbol (in SaComp: 0x7fffffff).
//
// lcp[0] = -1
// lcp[i] = lcp of str[sa[i-1]..$] and str[sa[i]..$].
//
// Verified by
//   - Codeforces 129 Div1 E
//-------------------------------------------------------------

struct SaComp {
	const int sp, *sr, srlen;
	SaComp(int sp, const vector<int>& sr) : sp(sp), sr(&sr[0]), srlen(sr.size()) {}
	bool operator()(int a, int b) const
	  { return make_pair(sr[a], a+sp<srlen?sr[a+sp]:0x7fffffff)
	         < make_pair(sr[b], b+sp<srlen?sr[b+sp]:0x7fffffff); }
};

template<typename RanIt>
vector<int> compute_suffix_array(RanIt beg, RanIt end)
{
	const int N = end - beg;

	vector<int> sa(N);
	vector<int> sort_rank(beg, end);
	for(int i=0; i<N; ++i)
		sa[i] = i;

	sort(sa.begin(), sa.end(), SaComp(0, sort_rank));
	for(int sorted_prefix=1; sorted_prefix<N; sorted_prefix*=2)
	{
		SaComp cmp(sorted_prefix, sort_rank);
		sort(sa.begin(), sa.end(), cmp);

		vector<int> block_id(N);
		for(int i=1; i<N; ++i)
			block_id[i] = block_id[i-1] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
		for(int i=0; i<N; ++i)
			sort_rank[sa[i]] = block_id[i];
	}
	return sa;
}

vector<int> inv_sa(const vector<int>& sa)
{
	vector<int> isa(sa.size());
	for(int i=0; i<sa.size(); ++i)
		isa[sa[i]] = i;
	return isa;
}

template<typename RanIte>
vector<int> longest_common_prefix(RanIte beg, RanIte end, const vector<int>& sa)
{
	const int N = sa.size();
	vector<int> lcp(N);
	vector<int> inv = inv_sa(sa);

	int len = 0;
	for(int i=0; i<N; ++i) {
		int sa_idx = inv[i];
		if( sa_idx == 0 )
			lcp[sa_idx] = -1;
		else {
			for(int k=sa[sa_idx-1]; i+len<N && k+len<N && *(beg+i+len)==*(beg+k+len);)
				++len;
			lcp[sa_idx] = len;
		}
		if(len) --len;
	}
	return lcp;
}