Artifact 24b4786c5875bcf17e6190dc9d122a18b12f0c95
//-------------------------------------------------------------
// 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;
}