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
CGR.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>
15
16
17namespace stringology {
18
19 namespace exact {
20
21
26 class CGR {
27 public:
32 template < class SymbolType >
34
35 };
36
37
38 template < class SymbolType >
41 const auto & text = subject.getContent();
42 const auto & pat = pattern.getContent();
43 size_t n = text.size(), m = pat.size();
44
45 size_t repSize, p , q ;
47 ext::tie( repSize , p , q ) = string::properties::Repetition::construct(pattern) ;
49
51 // for repSize == 0 or 1 use naive solution
52 if ( repSize == 0 || repSize == 1 ) {
53 for ( size_t i = 0 ; i <= n - m ; ++ i ) {
54 size_t j = 0 ;
55 while ( j < m && text[i + j ] == pat[j] ) ++ j ;
56 if ( j == m ) occ.insert(i) ;
57 }
59 return occ ;
60 }
61
62 size_t i = repSize/2 ;
63 while ( i <= n - m ) {
64 bool leftmostMismatch = std::equal(text.begin() + i + p , text.begin() + i + p + repSize/2 , text.begin() + i + q ) ;
65 if ( leftmostMismatch ) {
66 for ( size_t i_0 = i - repSize / 2 ; i_0 <= i ; ++ i_0 ){
67 if ( std::equal( pat.begin() , pat.end() , text.begin() + i_0 ) ) occ.insert(i_0) ;
68 }
69 }
70 i += repSize / 2 ;
71 }
72 // check last positions, where i jump into last window
73 for ( size_t j = i - repSize / 2 ; j <= n - m ; ++ j ) {
74 if ( std::equal( pat.begin() , pat.end() , text.begin() + j ) ) occ.insert(j) ;
75 }
77 return occ ;
78 }
79
80
81 } /* namespace exact */
82
83} /* namespace stringology */
84
Definition: set.hpp:44
Linear string.
Definition: LinearString.h:57
const ext::vector< SymbolType > & getContent() const &
Definition: LinearString.h:238
static ext::tuple< size_t, size_t, size_t > construct(const string::LinearString< SymbolType > &string)
Definition: Repetition.h:28
Definition: CGR.h:26
static ext::set< unsigned > match(const string::LinearString< SymbolType > &subject, const string::LinearString< SymbolType > &pattern)
Definition: CGR.h:39
int i
Definition: AllEpsilonClosure.h:118
q
Definition: SingleInitialStateEpsilonTransition.h:85
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
void start(measurements::stealth_string name, measurements::Type type)
Definition: measurements.cpp:14
void end()
Definition: measurements.cpp:19
Definition: ArithmeticCompression.h:18