Newer
Older
1
2
3
4
5
6
7
8
9
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
/*
* GoodSuffixShiftTable.h
*
* Created on: 23. 3. 2017
* Author: Jan Travnicek
*/
#ifndef _STRINGOLOGY_GOOD_SUFFIX_SHIFT_TABLE_H_
#define _STRINGOLOGY_GOOD_SUFFIX_SHIFT_TABLE_H_
#include <string/String.h>
#include <string/StringFeatures.h>
#include <core/multipleDispatch.hpp>
#include <vector>
#include <string/LinearString.h>
#include <string/properties/BorderArray.h>
#include <automaton/determinize/Determinize.h>
#include <automaton/simplify/EpsilonRemoverIncoming.h>
#include <stringology/exact/ExactFactorAutomaton.h>
namespace string {
namespace properties {
/**
* Computation of GSS table for BM from MI(E+\eps)-EVY course 2014
*/
class GoodSuffixShiftTable : public std::SingleDispatch < GoodSuffixShiftTable, std::vector < size_t >, const string::StringBase & > {
public:
/**
* Search for pattern in linear string.
* @return set set of occurences
*/
static std::vector < size_t > gss ( const string::String & pattern );
template < class SymbolType >
static std::vector < size_t > gss ( const string::LinearString < SymbolType > & pattern );
};
template < class SymbolType >
std::vector < size_t > GoodSuffixShiftTable::gss ( const string::LinearString < SymbolType > & pattern ) {
std::vector < SymbolType > content = pattern.getContent ( );
std::reverse ( content.begin ( ), content.end ( ) );
string::LinearString < SymbolType > reversed ( std::move ( content ) );
std::vector < unsigned > borderArray = string::properties::BorderArray::construct ( reversed );
size_t max = reversed.getContent ( ).size ( ) - borderArray.back ( );
automaton::DFA < DefaultSymbolType, std::set < unsigned > > factorAutomaton = automaton::determinize::Determinize::determinize ( automaton::simplify::EpsilonRemoverIncoming::remove ( stringology::exact::ExactFactorAutomaton::construct ( reversed ) ) );
std::vector < size_t > result;
std::set < unsigned > state = factorAutomaton.getInitialState ( );
result.push_back ( 1 );
for ( const SymbolType & symbol : reversed.getContent ( ) ) {
state = factorAutomaton.getTransitions ( ).find ( std::make_pair ( std::move ( state ), symbol ) )->second;
if ( state.size ( ) >= 2 ) {
unsigned first = * state.begin ( );
unsigned second = * std::next ( state.begin ( ) );
result.push_back ( second - first );
} else {
result.push_back ( max );
}
}
return result;
}
} /* namespace properties */
} /* namespace string */
#endif /* _STRINGOLOGY_GOOD_SUFFIX_SHIFT_TABLE_H_ */