cd0467fefc 2012-07-22 kinaba: //------------------------------------------------------------- cd0467fefc 2012-07-22 kinaba: // Suffix Array cd0467fefc 2012-07-22 kinaba: // O(N log N) construction by Larsson-Sadakane cd0467fefc 2012-07-22 kinaba: // from http://www.prefield.com/algorithm/string/suffix_array.html cd0467fefc 2012-07-22 kinaba: // cd0467fefc 2012-07-22 kinaba: // compute_suffix_array("baca") cd0467fefc 2012-07-22 kinaba: // = {"aca" < "a$" < "baca" < "ca"} = {1,3,0,2} cd0467fefc 2012-07-22 kinaba: // EOS is set to be the largest symbol (in SaComp: 0x7fffffff). cd0467fefc 2012-07-22 kinaba: // cd0467fefc 2012-07-22 kinaba: // lcp[0] = -1 cd0467fefc 2012-07-22 kinaba: // lcp[i] = lcp of str[sa[i-1]..$] and str[sa[i]..$]. cd0467fefc 2012-07-22 kinaba: // cd0467fefc 2012-07-22 kinaba: // Verified by cd0467fefc 2012-07-22 kinaba: // - Codeforces 129 Div1 E cd0467fefc 2012-07-22 kinaba: //------------------------------------------------------------- cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: struct SaComp { cd0467fefc 2012-07-22 kinaba: const int sp, *sr, srlen; cd0467fefc 2012-07-22 kinaba: SaComp(int sp, const vector<int>& sr) : sp(sp), sr(&sr[0]), srlen(sr.size()) {} cd0467fefc 2012-07-22 kinaba: bool operator()(int a, int b) const cd0467fefc 2012-07-22 kinaba: { return make_pair(sr[a], a+sp<srlen?sr[a+sp]:0x7fffffff) cd0467fefc 2012-07-22 kinaba: < make_pair(sr[b], b+sp<srlen?sr[b+sp]:0x7fffffff); } cd0467fefc 2012-07-22 kinaba: }; cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: template<typename RanIt> cd0467fefc 2012-07-22 kinaba: vector<int> compute_suffix_array(RanIt beg, RanIt end) cd0467fefc 2012-07-22 kinaba: { cd0467fefc 2012-07-22 kinaba: const int N = end - beg; cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: vector<int> sa(N); cd0467fefc 2012-07-22 kinaba: vector<int> sort_rank(beg, end); cd0467fefc 2012-07-22 kinaba: for(int i=0; i<N; ++i) cd0467fefc 2012-07-22 kinaba: sa[i] = i; cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: sort(sa.begin(), sa.end(), SaComp(0, sort_rank)); cd0467fefc 2012-07-22 kinaba: for(int sorted_prefix=1; sorted_prefix<N; sorted_prefix*=2) cd0467fefc 2012-07-22 kinaba: { cd0467fefc 2012-07-22 kinaba: SaComp cmp(sorted_prefix, sort_rank); cd0467fefc 2012-07-22 kinaba: sort(sa.begin(), sa.end(), cmp); cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: vector<int> block_id(N); cd0467fefc 2012-07-22 kinaba: for(int i=1; i<N; ++i) cd0467fefc 2012-07-22 kinaba: block_id[i] = block_id[i-1] + (cmp(sa[i-1], sa[i]) ? 1 : 0); cd0467fefc 2012-07-22 kinaba: for(int i=0; i<N; ++i) cd0467fefc 2012-07-22 kinaba: sort_rank[sa[i]] = block_id[i]; cd0467fefc 2012-07-22 kinaba: } cd0467fefc 2012-07-22 kinaba: return sa; cd0467fefc 2012-07-22 kinaba: } cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: vector<int> inv_sa(const vector<int>& sa) cd0467fefc 2012-07-22 kinaba: { cd0467fefc 2012-07-22 kinaba: vector<int> isa(sa.size()); cd0467fefc 2012-07-22 kinaba: for(int i=0; i<sa.size(); ++i) cd0467fefc 2012-07-22 kinaba: isa[sa[i]] = i; cd0467fefc 2012-07-22 kinaba: return isa; cd0467fefc 2012-07-22 kinaba: } cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: template<typename RanIte> cd0467fefc 2012-07-22 kinaba: vector<int> longest_common_prefix(RanIte beg, RanIte end, const vector<int>& sa) cd0467fefc 2012-07-22 kinaba: { cd0467fefc 2012-07-22 kinaba: const int N = sa.size(); cd0467fefc 2012-07-22 kinaba: vector<int> lcp(N); cd0467fefc 2012-07-22 kinaba: vector<int> inv = inv_sa(sa); cd0467fefc 2012-07-22 kinaba: cd0467fefc 2012-07-22 kinaba: int len = 0; cd0467fefc 2012-07-22 kinaba: for(int i=0; i<N; ++i) { cd0467fefc 2012-07-22 kinaba: int sa_idx = inv[i]; cd0467fefc 2012-07-22 kinaba: if( sa_idx == 0 ) cd0467fefc 2012-07-22 kinaba: lcp[sa_idx] = -1; cd0467fefc 2012-07-22 kinaba: else { cd0467fefc 2012-07-22 kinaba: for(int k=sa[sa_idx-1]; i+len<N && k+len<N && *(beg+i+len)==*(beg+k+len);) cd0467fefc 2012-07-22 kinaba: ++len; cd0467fefc 2012-07-22 kinaba: lcp[sa_idx] = len; cd0467fefc 2012-07-22 kinaba: } cd0467fefc 2012-07-22 kinaba: if(len) --len; cd0467fefc 2012-07-22 kinaba: } cd0467fefc 2012-07-22 kinaba: return lcp; cd0467fefc 2012-07-22 kinaba: }