Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
LevenshteinSequenceMatchingAutomaton.h
Go to the documentation of this file.
1
6#pragma once
7
10#include <string/LinearString.h>
12
13
14namespace stringology {
15
16namespace matching {
17
19public:
25 template < class SymbolType >
27
33 template < class SymbolType >
35
36};
37
38template < class SymbolType >
41
42 for (unsigned int j = 0; j<allowed_errors + 1; j++) {
43 for (unsigned int i = j; i<pattern.getContent().size(); i++) {
44 auto current_state = ext::make_pair(i, j);
45
46 for (const SymbolType & symbol : pattern.getAlphabet()) {
47 if (symbol != pattern.getContent()[i]) {
48 result.addTransition(current_state, symbol, current_state);
49 }
50 }
51 }
52 }
53
54 return result;
55}
56
57template < class SymbolType >
60
61 const SymbolType & wildcard = pattern.getWildcardSymbol();
62 ext::set<SymbolType> alphabet_without_wildcard = pattern.getAlphabet();
63 alphabet_without_wildcard.erase(wildcard);
64
65 for (unsigned int j = 0; j<allowed_errors + 1; j++) {
66 for (unsigned int i = j; i<pattern.getContent().size(); i++) {
67 auto current_state = ext::make_pair(i, j);
68
69 if (pattern.getContent()[i] != wildcard) {
70 for (const SymbolType & symbol : alphabet_without_wildcard) {
71 if (symbol != pattern.getContent()[i]) {
72 result.addTransition(current_state, symbol, current_state);
73 }
74 }
75 }
76 }
77 }
78
79 return result;
80}
81
82
83} /* namespace matching */
84
85} /* namespace stringology */
86
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
Definition: set.hpp:44
Linear string.
Definition: LinearString.h:57
const ext::set< SymbolType > & getAlphabet() const &
Definition: LinearString.h:103
const ext::vector< SymbolType > & getContent() const &
Definition: LinearString.h:238
Linear wildcard string.
Definition: WildcardLinearString.h:44
const ext::vector< SymbolType > & getContent() const &
Definition: WildcardLinearString.h:279
const SymbolType & getWildcardSymbol() const &
Definition: WildcardLinearString.h:139
const ext::set< SymbolType > & getAlphabet() const &
Definition: WildcardLinearString.h:112
static automaton::EpsilonNFA< SymbolType, ext::pair< unsigned int, unsigned int > > construct(const string::LinearString< SymbolType > &pattern, unsigned int allowed_errors)
Definition: LevenshteinMatchingAutomaton.h:40
Definition: LevenshteinSequenceMatchingAutomaton.h:18
static automaton::EpsilonNFA< SymbolType, ext::pair< unsigned int, unsigned int > > construct(const string::LinearString< SymbolType > &pattern, unsigned int allowed_errors)
Definition: LevenshteinSequenceMatchingAutomaton.h:39
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
for(const StateType &state :fsm.getStates()) renamingData.insert(std Rename::RenamedAutomaton< T > result(renamingData.at(fsm.getInitialState()))
Definition: Rename.h:253
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Definition: ArithmeticCompression.h:18