6 template <class Iterator, class DCSampler, class RankIterator>
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)
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];
30 // last_lcp == lcp((suf-last), pivot) &&
31 // last_less == (suf-last)+last_lcp == str_end ||
32 // (suf-last)[last_lcp] < pivot[last_lcp]
35 if (suf==str_end) return true;
37 last_lcp = pivot_end-pivot;
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]);
51 if (last_lcp < last || last_lcp == last+lcp[last]) {
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]) {
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);
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;
71 } else if (last_lcp > last+lcp[last]) {
74 } else if (last_lcp < last+lcp[last]) {
80 //std::cout << " result=" << result << std::endl;
84 //81 0 212 cabcbacacabcbacacabcbacacabcbacacabcbaca
98 std::vector<char> less;
100 const DCSampler& dcsampler;
101 RankIterator dcranks;
105 int length = pivot_end-pivot;
111 std::vector<int> shift(length+1);
115 while ( j < length && pivot[i] == pivot[j] ) {
120 if (j == length) break;
123 } while ( i != -1 && pivot[i] != pivot[j] );
124 if (i==-1) { ++i; ++j; }
127 std::copy (shift.begin(), shift.end(),
128 std::ostream_iterator<int>(std::cout, " "));
129 std::cout << std::endl;
132 lcp.resize(length+1);
133 less.resize(length+1);
139 while (j <= length) {
140 while ( j < length && pivot[i] == pivot[j] ) {
143 if ( j == length || pivot[i] < pivot[j] ) {
156 } else if (lcp[k-i] == i) {
158 } else if (lcp[k-i] < i) {
160 less[j-i] = less[k-i];
162 lcp[j-i] = i; // i == lcp[j-k]
163 less[j-i] = less[j-k];
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;