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 // Range Minimum Query 2 // Range Minimum Query 3 // O(N log N) construction 3 // O(N log N) construction 4 // O(1) per each query | 4 // O(log N) per each query 5 // returns the LEFTMOST/ALL minimum index (I hope) < 6 // 5 // 7 // Verified by 6 // Verified by 8 // - SRM337 Div1 LV2 7 // - SRM337 Div1 LV2 9 // - SRM431 Div1 LV3 8 // - SRM431 Div1 LV3 > 9 // - Codeforces 129 Div1 E 10 //------------------------------------------------------------- 10 //------------------------------------------------------------- 11 11 12 template<typename T> 12 template<typename T> 13 struct RMQ 13 struct RMQ 14 { 14 { 15 vector< vector<int> > rm; 15 vector< vector<int> > rm; 16 vector<T> d; 16 vector<T> d; ................................................................................................................................................................................ 26 rm.push_back( rm[k-1] ); 26 rm.push_back( rm[k-1] ); 27 for(int x=0; x+(1<<k-1)<n; ++x) 27 for(int x=0; x+(1<<k-1)<n; ++x) 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] ) 28 if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] ) 29 rm[k][x] = rm[k-1][x + (1<<k-1)]; 29 rm[k][x] = rm[k-1][x + (1<<k-1)]; 30 } 30 } 31 } 31 } 32 32 > 33 // min {i in [L,R] | d[i] is minumum among d[L..R]} 33 int operator()(int L, int R) const { // inclusive | 34 int operator()(int L, int R) const { 34 int k=0; 35 int k=0; 35 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 36 for(; L+(1<<k) < R-(1<<k)+1; ++k) {} 36 LL i = rm[k][L]; | 37 int i = rm[k][L]; 37 LL j = rm[k][R-(1<<k)+1]; | 38 int j = rm[k][R-(1<<k)+1]; 38 return (d[i]<=d[j] ? i : j); 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 vector<int> all(int L, int R) const { 43 vector<int> all(int L, int R) const { 42 vector<int> ans; 44 vector<int> ans; 43 int minValue = d[(*this)(L, R)]; 45 int minValue = d[(*this)(L, R)]; 44 while( L <= R ) { 46 while( L <= R ) { 45 int C = (*this)(L, R); 47 int C = (*this)(L, R); 46 if( minValue < d[C] ) 48 if( minValue < d[C] ) 47 break; 49 break; 48 ans.push_back(C); 50 ans.push_back(C); 49 L = C+1; 51 L = C+1; 50 } 52 } 51 return ans; 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.siz > 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 : > 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+le > 72 ++len; > 73 lcp[sa_idx] = len; > 74 } > 75 if(len) --len; > 76 } > 77 return lcp; > 78 }