Overview
| SHA1 Hash: | cd0467fefc5f0242aaaeaa3ab0ec86aefc80983b |
|---|---|
| Date: | 2012-07-22 18:00:41 |
| User: | kinaba |
| Comment: | Suffix Array. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified lib/dataStructure/rmq.cpp from [a0dd84df47a73891] to [b1b5e925fa550aa0].
1 1 //------------------------------------------------------------- 2 2 // Range Minimum Query 3 3 // O(N log N) construction 4 -// O(1) per each query 5 -// returns the LEFTMOST/ALL minimum index (I hope) 4 +// O(log N) per each query 6 5 // 7 6 // Verified by 8 7 // - SRM337 Div1 LV2 9 8 // - SRM431 Div1 LV3 9 +// - Codeforces 129 Div1 E 10 10 //------------------------------------------------------------- 11 11 12 12 template<typename T> 13 13 struct RMQ 14 14 { 15 15 vector< vector<int> > rm; 16 16 vector<T> d; ................................................................................ 26 26 rm.push_back( rm[k-1] ); 27 27 for(int x=0; x+(1<<k-1)<n; ++x) 28 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] ) 29 29 rm[k][x] = rm[k-1][x + (1<<k-1)]; 30 30 } 31 31 } 32 32 33 - int operator()(int L, int R) const { // inclusive 33 + // min {i in [L,R] | d[i] is minumum among d[L..R]} 34 + int operator()(int L, int R) const { 34 35 int k=0; 35 36 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 36 - LL i = rm[k][L]; 37 - LL j = rm[k][R-(1<<k)+1]; 37 + int i = rm[k][L]; 38 + int j = rm[k][R-(1<<k)+1]; 38 39 return (d[i]<=d[j] ? i : j); 39 40 } 40 41 42 + // {i in [L,R] | d[i] is minumum among d[L..R]} 41 43 vector<int> all(int L, int R) const { 42 44 vector<int> ans; 43 45 int minValue = d[(*this)(L, R)]; 44 46 while( L <= R ) { 45 47 int C = (*this)(L, R); 46 48 if( minValue < d[C] ) 47 49 break; 48 50 ans.push_back(C); 49 51 L = C+1; 50 52 } 51 53 return ans; 52 54 } 55 + 56 + // max {i in [L,R] | d[i]<X}, or -1 57 + int rightmost_less_than_X(int L, int R, T X) const { 58 + if(L>R) return -1; 59 + 60 + int k=0; 61 + for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 62 + 63 + int i = rm[k][L]; 64 + int j = rm[k][R-(1<<k)+1]; 65 + if( !(d[i]<X || d[j]<X) ) 66 + return -1; 67 + if( d[j] < X ) 68 + L = R-(1<<k)+1; 69 + 70 + for(; k; --k) { // Answer is in [L, L+(1<<k)) 71 + i = rm[k-1][L]; 72 + j = rm[k-1][L+(1<<k-1)]; 73 + if( d[j] < X ) 74 + L += 1<<k-1; 75 + } 76 + return L; 77 + } 78 + 79 + // min {i in [L,R] | d[i]<X}, or -1 80 + int leftmost_less_than_X(int L, int R, T X) const { 81 + if(L>R) return -1; 82 + 83 + int k=0; 84 + for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 85 + 86 + int i = rm[k][L]; 87 + int j = rm[k][R-(1<<k)+1]; 88 + if( !(d[i]<X || d[j]<X) ) 89 + return -1; 90 + if( !(d[i] < X) ) 91 + L = R-(1<<k)+1; 92 + 93 + for(; k; --k) { // Answer is in [L, L+(1<<k)) 94 + i = rm[k-1][L]; 95 + j = rm[k-1][L+(1<<k-1)]; 96 + if( !(d[i] < X) ) 97 + L += 1<<k-1; 98 + } 99 + return L; 100 + } 53 101 };
Added lib/dataStructure/suffixArray.cpp version [24b4786c5875bcf1]
1 +//------------------------------------------------------------- 2 +// Suffix Array 3 +// O(N log N) construction by Larsson-Sadakane 4 +// from http://www.prefield.com/algorithm/string/suffix_array.html 5 +// 6 +// compute_suffix_array("baca") 7 +// = {"aca" < "a$" < "baca" < "ca"} = {1,3,0,2} 8 +// EOS is set to be the largest symbol (in SaComp: 0x7fffffff). 9 +// 10 +// lcp[0] = -1 11 +// lcp[i] = lcp of str[sa[i-1]..$] and str[sa[i]..$]. 12 +// 13 +// Verified by 14 +// - Codeforces 129 Div1 E 15 +//------------------------------------------------------------- 16 + 17 +struct SaComp { 18 + const int sp, *sr, srlen; 19 + SaComp(int sp, const vector<int>& sr) : sp(sp), sr(&sr[0]), srlen(sr.size()) {} 20 + bool operator()(int a, int b) const 21 + { return make_pair(sr[a], a+sp<srlen?sr[a+sp]:0x7fffffff) 22 + < make_pair(sr[b], b+sp<srlen?sr[b+sp]:0x7fffffff); } 23 +}; 24 + 25 +template<typename RanIt> 26 +vector<int> compute_suffix_array(RanIt beg, RanIt end) 27 +{ 28 + const int N = end - beg; 29 + 30 + vector<int> sa(N); 31 + vector<int> sort_rank(beg, end); 32 + for(int i=0; i<N; ++i) 33 + sa[i] = i; 34 + 35 + sort(sa.begin(), sa.end(), SaComp(0, sort_rank)); 36 + for(int sorted_prefix=1; sorted_prefix<N; sorted_prefix*=2) 37 + { 38 + SaComp cmp(sorted_prefix, sort_rank); 39 + sort(sa.begin(), sa.end(), cmp); 40 + 41 + vector<int> block_id(N); 42 + for(int i=1; i<N; ++i) 43 + block_id[i] = block_id[i-1] + (cmp(sa[i-1], sa[i]) ? 1 : 0); 44 + for(int i=0; i<N; ++i) 45 + sort_rank[sa[i]] = block_id[i]; 46 + } 47 + return sa; 48 +} 49 + 50 +vector<int> inv_sa(const vector<int>& sa) 51 +{ 52 + vector<int> isa(sa.size()); 53 + for(int i=0; i<sa.size(); ++i) 54 + isa[sa[i]] = i; 55 + return isa; 56 +} 57 + 58 +template<typename RanIte> 59 +vector<int> longest_common_prefix(RanIte beg, RanIte end, const vector<int>& sa) 60 +{ 61 + const int N = sa.size(); 62 + vector<int> lcp(N); 63 + vector<int> inv = inv_sa(sa); 64 + 65 + int len = 0; 66 + for(int i=0; i<N; ++i) { 67 + int sa_idx = inv[i]; 68 + if( sa_idx == 0 ) 69 + lcp[sa_idx] = -1; 70 + else { 71 + for(int k=sa[sa_idx-1]; i+len<N && k+len<N && *(beg+i+len)==*(beg+k+len);) 72 + ++len; 73 + lcp[sa_idx] = len; 74 + } 75 + if(len) --len; 76 + } 77 + return lcp; 78 +}