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
QuickSearchBadCharacterShiftTable.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <set>
9#include <map>
10
11#include <string/LinearString.h>
12
13namespace string {
14
15namespace properties {
16
21public:
26 template < class SymbolType >
28
29};
30
31template < class SymbolType >
34
35 /* Initialization of BCS. */
36 for(const SymbolType & symbol : pattern.getAlphabet ( ) )
37 bcs.insert(std::make_pair(symbol, pattern.getContent().size() + 1));
38
39 /* Filling out BCS. */
40 for(size_t i = 0; i < pattern.getContent().size(); i++)
41 bcs [ pattern.getContent ( ) [ i ] ] = pattern.getContent().size() - i;
42
43 return bcs;
44}
45
46} /* namespace properties */
47
48} /* namespace string */
49
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
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
Definition: QuickSearchBadCharacterShiftTable.h:20
static ext::map< SymbolType, size_t > qsbcs(const string::LinearString< SymbolType > &pattern)
Definition: QuickSearchBadCharacterShiftTable.h:32
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
Definition: RandomStringFactory.cpp:12