Newer
Older
Tomáš Pecka
committed
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
/*
* Author: Radovan Cerveny
*/
#ifndef NONDETERMINISTIC_EXACT_SUFFIX_EPSILON_AUTOMATON_H_
#define NONDETERMINISTIC_EXACT_SUFFIX_EPSILON_AUTOMATON_H_
#include <automaton/FSM/EpsilonNFA.h>
#include <string/LinearString.h>
namespace stringology {
namespace indexing {
class NondeterministicExactSuffixEpsilonAutomaton {
public:
/**
* Nondeterministic construction of nondeterministic suffix automaton for given pattern.
* @return nondeterministic suffix automaton for given pattern.
*/
template < class SymbolType >
static automaton::EpsilonNFA < SymbolType, unsigned > construct ( const string::LinearString < SymbolType > & pattern );
};
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, unsigned > NondeterministicExactSuffixEpsilonAutomaton::construct ( const string::LinearString < SymbolType > & pattern ) {
automaton::EpsilonNFA < SymbolType, unsigned > nfaSuffixAutomaton ( 0 );
nfaSuffixAutomaton.setInputAlphabet ( pattern.getAlphabet ( ) );
unsigned i = 0;
for ( const SymbolType & symbol : pattern.getContent ( ) ) {
nfaSuffixAutomaton.addState ( ++ i );
nfaSuffixAutomaton.addTransition ( i - 1, symbol, i );
nfaSuffixAutomaton.addTransition ( 0, i );
}
nfaSuffixAutomaton.addFinalState ( i );
return nfaSuffixAutomaton;
}
} /* namespace indexing */
} /* namespace stringology */
#endif /* NONDETERMINISTIC_EXACT_SUFFIX_EPSILON_AUTOMATON_H_ */