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
GalilSeiferas.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <alib/measure>
9
10#include <alib/set>
11#include <alib/vector>
12
13#include <string/LinearString.h>
14#include <algorithm>
16#include <alphabet/EndSymbol.h>
17
18
19namespace stringology {
20
21 namespace exact {
22
23
29 public:
34 template < class SymbolType >
36
37 };
38
39 size_t div_up (const size_t &x ,const size_t &y ) {
40 return ( x % y == 1 ) ? x / y + 1 : x / y ;
41 }
42
43 template < class SymbolType >
46
47 // add terminating symbol to text
48 SymbolType endSymbol = common::createUnique ( alphabet::EndSymbol::instance < SymbolType > ( ), subject.getAlphabet ( ) );
49 ext::vector < SymbolType > content = subject.getContent ( );
50 content.push_back ( endSymbol );
51
52 // add terminating symbol to pattern
53 SymbolType endSymbol2 = common::createUnique ( alphabet::EndSymbol::instance < SymbolType > ( ), pattern.getAlphabet ( ) );
54 ext::vector < SymbolType > contentPatt = pattern.getContent ( );
55 contentPatt.push_back ( endSymbol );
56
57 std::vector y = content ;
58 std::vector x = contentPatt ;
59 size_t n = y.size() - 1 , m = x.size() - 1 ;
60
61 unsigned k = 4 ;
62 size_t p = 0 , q = 0 ;
63 size_t s = 0 , p1 = 1 , q1 = 0 ;
64 size_t p2 = 0 , q2 = 0 ;
65
66
68 newp1:
69 while( x[s + p1 + q1] == x[s + q1] ) ++ q1 ;
70 if ( p1 + q1 >= k * p1 ) {
71 p2 = q1 ;
72 q2 = 0 ;
73 goto newp2 ;
74 }
75
76
77 if ( s + p1 + q1 == m ) goto search ;
78 p1 += std::max( static_cast < size_t > ( 1 ) , div_up ( q1 , k ) ) ;
79 q1 = 0 ;
80 goto newp1 ;
81
82 newp2:
83 while( x[s + p2 + q2] == x[s + q2] && p2 + q2 < k* p2 ) ++ q2 ;
84 if ( p2 + q2 == k * p2 ) goto parse ;
85 if ( s + p2 + q2 == m ) goto search ;
86 if ( q2 == p1 + q1 ) {
87 p2 += p1 ;
88 q2 -= p1 ;
89 } else {
90 p2 += std::max ( static_cast < size_t > ( 1 ) , div_up(q2 , k)) ;
91 q2 = 0 ;
92 }
93 goto newp2 ;
94
95 parse:
96 while ( x[s + p1 + q1] == x[s + q1]) ++ q1 ;
97 while ( p1 + q1 >= k * p1 ) {
98 s += p1 ;
99 q1 -= p1 ;
100 }
101 p1 += std::max ( static_cast < size_t > ( 1 ) , div_up(q1 , k ));
102 q1 = 0 ;
103 if ( p1 < p2 ) goto parse ;
104 else goto newp1 ;
105
106 search:
107 while ( p <= n - m ) {
108 while ( p + s + q < n && y[p + s + q] == x[s + q]) ++q;
109 if (q == m - s && std::equal( y.begin() + p, y.begin() + p + s , x.begin())) occ.insert(p);
110 if (q == p1 + q1) {
111 p += p1;
112 q -= p1;
113 } else {
114 p += std::max ( static_cast < size_t > ( 1 ), div_up(q, k));
115 q = 0;
116 }
117 }
119 return occ ;
120 }
121
122
123 } /* namespace exact */
124
125} /* namespace stringology */
126
Definition: set.hpp:44
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
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: GalilSeiferas.h:28
static ext::set< unsigned > match(const string::LinearString< SymbolType > &subject, const string::LinearString< SymbolType > &pattern)
Definition: GalilSeiferas.h:44
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
q
Definition: SingleInitialStateEpsilonTransition.h:85
T createUnique(T object, const Alphabets &... alphabets)
Definition: createUnique.hpp:46
constexpr const T & max(const T &a)
Root case of maximum computation. The maximum from one value is the value itself.
Definition: algorithm.hpp:278
void start(measurements::stealth_string name, measurements::Type type)
Definition: measurements.cpp:14
void end()
Definition: measurements.cpp:19
size_t div_up(const size_t &x, const size_t &y)
Definition: GalilSeiferas.h:39
Definition: ArithmeticCompression.h:18