dcover/kmpsplit.hpp

   1
   2 #include <vector>
   3 #include <iostream>
   4 #include <iterator>
   5
   6 template <class Iterator, class DCSampler, class RankIterator>
   7 class kmp_split {
   8 public:
   9
  10   kmp_split(Iterator s, Iterator se, Iterator p,
  11             const DCSampler& d, RankIterator r)
  12     : str(s), str_end(se), suf(str), pivot(p), pivot_end(p+d.period()-1),
  13       last(1), last_lcp(0), dcsampler(d), dcranks(r)
  14   {
  15     preprocess();
  16   }
  17
  18 private:
  19
  20   bool dc_less(Iterator a, Iterator b) const {
  21     std::pair<int,int> rep = dcsampler.pair(a-str, b-str);
  22     return dcranks[rep.first] <= dcranks[rep.second];
  23   }
  24
  25 public:
  26
  27   bool is_next_less() {
  28     // state:
  29     // suf == str_end ||
  30     // last_lcp == lcp((suf-last), pivot) &&
  31     // last_less == (suf-last)+last_lcp == str_end ||
  32     //              (suf-last)[last_lcp] < pivot[last_lcp]
  33
  34     bool result = true;
  35     if (suf==str_end) return true;
  36     if (suf==pivot) {
  37       last_lcp = pivot_end-pivot;
  38       last_less = false;
  39       ++suf; last=1;
  40       return false;
  41     }
  42
  43     /*
  44     std::cout << " last=" << last
  45               << " last_lcp=" << last_lcp
  46               << " last+lcp[last]=" << last+lcp[last]
  47               << " last_less=" << last_less
  48               << " less[last]=" << bool(less[last]);
  49     */
  50
  51     if (last_lcp < last || last_lcp == last+lcp[last]) {
  52       int lcp;
  53       if (last_lcp < last) lcp = 0;
  54       else lcp = last_lcp - last;
  55       while (suf+lcp != str_end && pivot+lcp != pivot_end
  56              && suf[lcp]==pivot[lcp]) {
  57         ++lcp;
  58       }
  59       /*
  60       std::cout << " lcp=" << lcp
  61                 << " suf+lcp-str=" << suf+lcp-str
  62                 << " str_end-str=" << str_end-str
  63                 << " suf+lcp==str=" << (suf+lcp==str);
  64       */
  65       result = (suf+lcp==str_end)
  66         || (pivot+lcp==pivot_end ? dc_less(suf, pivot) : suf[lcp] < pivot[lcp]);
  67       //std::cout << " result=" << result << std::endl;
  68       last_lcp = lcp;
  69       last_less = result;
  70       ++suf; last = 1;
  71     } else if (last_lcp > last+lcp[last]) {
  72       result = !less[last];
  73       ++suf; ++last;
  74     } else if (last_lcp < last+lcp[last]) {
  75       result = last_less;
  76       last_lcp -= last;
  77       ++suf; last = 1;
  78     }
  79
  80     //std::cout << " result=" << result << std::endl;
  81     return result;
  82   }
  83
  84   //81   0      212 cabcbacacabcbacacabcbacacabcbacacabcbaca
  85
  86 private:
  87   Iterator str;
  88   Iterator str_end;
  89   Iterator suf;
  90   Iterator pivot;
  91   Iterator pivot_end;
  92
  93   int last;
  94   int last_lcp;
  95   bool last_less;
  96
  97   std::vector<int> lcp;
  98   std::vector<char> less;
  99
 100   const DCSampler& dcsampler;
 101   RankIterator dcranks;
 102
 103   void preprocess() {
 104
 105     int length = pivot_end-pivot;
 106
 107     int i = 0;
 108     int j = 1;
 109
 110     /*
 111     std::vector<int> shift(length+1);
 112     shift[0] = -1;
 113
 114     while (true) {
 115       while ( j < length && pivot[i] == pivot[j] ) {
 116         shift[j] = shift[i];
 117         ++i; ++j;
 118       }
 119       shift[j] = i;
 120       if (j == length) break;
 121       do {
 122         i = shift[i];
 123       } while ( i != -1 && pivot[i] != pivot[j] );
 124       if (i==-1) { ++i; ++j; }
 125     }
 126
 127     std::copy (shift.begin(), shift.end(),
 128                std::ostream_iterator<int>(std::cout, " "));
 129     std::cout << std::endl;
 130     */
 131
 132     lcp.resize(length+1);
 133     less.resize(length+1);
 134
 135     lcp[0] = length;
 136     less[0] = 0;
 137     i = 0; j = 1;
 138
 139     while (j <= length) {
 140       while ( j < length && pivot[i] == pivot[j] ) {
 141         ++i; ++j;
 142       }
 143       if ( j == length || pivot[i] < pivot[j] ) {
 144         lcp[j-i] = i;
 145         less[j-i] = 1;
 146       } else {
 147         lcp[j-i] = i;
 148         less[j-i] = 0;
 149       }
 150       int k = i;
 151       do {
 152         --i;
 153         if (i == -1) {
 154           ++i; ++j;
 155           break;
 156         } else if (lcp[k-i] == i) {
 157           break;
 158         } else if (lcp[k-i] < i) {
 159           lcp[j-i] = lcp[k-i];
 160           less[j-i] = less[k-i];
 161         } else {
 162           lcp[j-i] = i; // i == lcp[j-k]
 163           less[j-i] = less[j-k];
 164         }
 165       } while (true);
 166     }
 167
 168     /*
 169     std::copy (lcp.begin(), lcp.end(),
 170                std::ostream_iterator<int>(std::cout, " "));
 171     std::cout << std::endl;
 172     std::copy (less.begin(), less.end(),
 173                std::ostream_iterator<int>(std::cout, " "));
 174     std::cout << std::endl;
 175     */
 176   }
 177
 178
 179 };
 180
 181
 182 /*
 183
 184 gagcgag
 185 gagcgag 7 0
 186  g      0 0
 187   ga    1 1
 188    g    0 0
 189     gag 3 1
 190      g  0 0
 191       g 1 1
 192         0 1
 193
 194 aagagcgagta
 195
 196 */