- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <utility>
#include <sstream>
#include <assert.h>
using namespace std;
struct PeriodDescription{
size_t length, repeat_amount, last_items_amount;
/*friend ostream& operator<<(ostream& os, const PeriodDescription& s){
os<<" (PeriodDescription){"<<s.length<<", "<<s.repeat_amount<<", "<<s.last_items_amount<<"} ";
return os;
}*/
};
/*template<class C>
string co(C&& c){
ostringstream r;
r<<" (C) {";
copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(r, ", "));
r<<"}; ";
return move(r.str());
}*/
vector<PeriodDescription> find_repeat_sequences_since_begin(const string& sequence){
vector<PeriodDescription> result;
if(sequence.empty())
return result;
auto position_at_last_period=sequence.begin();
const char first_item = *position_at_last_period;
const auto after_last=sequence.end();
auto position_at_current_period = position_at_last_period;
while(true){
position_at_last_period=sequence.begin();
position_at_current_period = find(next(position_at_current_period), after_last, first_item);
PeriodDescription new_period {size_t(distance(position_at_last_period, position_at_current_period)), 1, 0};
while(position_at_current_period!=after_last && *position_at_last_period==*position_at_current_period){
++position_at_last_period; ++position_at_current_period;
if(++new_period.last_items_amount>=new_period.length){
new_period.last_items_amount = 0;
++new_period.repeat_amount;
}
}
if(new_period.repeat_amount==1 && new_period.last_items_amount==0)
return result;
result.push_back(new_period);
if(position_at_current_period==after_last)
return result;
}
}
vector<size_t> generate_FSM_failJumpIndices(const vector<PeriodDescription>& periodDescriptions, const size_t stringLength){
vector<size_t> r(stringLength+1);
for(const auto& pd : periodDescriptions){
for(size_t periodIndex=1; periodIndex<pd.repeat_amount; ++periodIndex)
for(size_t indexAtPeriod=0; indexAtPeriod<pd.length; ++indexAtPeriod)
r[(periodIndex*pd.length)+indexAtPeriod]=(periodIndex-1)*pd.length + indexAtPeriod;
for(size_t indexAtAfterPeriods=0; indexAtAfterPeriods<pd.last_items_amount; ++indexAtAfterPeriods)
r[pd.length*pd.repeat_amount+indexAtAfterPeriods]=pd.length*(pd.repeat_amount-1)+indexAtAfterPeriods;
}
return r;
}
vector<size_t> make_FSM_failJumpIndices(const string& sequence){
return generate_FSM_failJumpIndices(find_repeat_sequences_since_begin(sequence), sequence.size());
}
class FSM_for_find_equal_ranges{
size_t state;
vector<size_t> failJumpIndices;
string sequence;
string::const_iterator find_next(string::const_iterator checkPosition, const string::const_iterator last){
struct atReturn{
size_t& state;
~atReturn(){state = 0;}
}nullify{state};
if(checkPosition==last)
return last;
if(sequence.empty())
return next(checkPosition);
if(size_t(distance(checkPosition, last))<sequence.size())
return last;
while(true){
if(checkPosition==last)
return last;
if(*checkPosition==sequence[state])
++state;
else
state=failJumpIndices[state];
++checkPosition;
if(state>=sequence.size())
return prev(checkPosition, sequence.size());
}
}
public:
template<class T>
FSM_for_find_equal_ranges(T&& sequence):
Follow us!