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
QuiteNaive.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
15
16namespace stringology {
17
18 namespace exact {
19
20
27 public:
32 template < class SymbolType >
34
35 };
36
37 template < class SymbolType >
40 const auto & text = subject.getContent();
41 const auto & pat = pattern.getContent();
42 size_t n = text.size(), m = pat.size();
43
45 // Preprocessing
46 size_t gamma = 1 , delta = 1 ;
47 while ( delta < m && pat[m-1] != pat[m-1-delta]) ++ delta;
48 while ( gamma < m && pat[m-1] == pat[m-1-gamma]) ++ gamma;
50
52 // Searching
53 size_t s = 0;
54 while ( s <= n - m ){
55 if ( pat[m-1] != text[s+m-1] ) s += gamma;
56 else {
57 ssize_t j = m - 2;
58 while ( j >= 0 && pat[j] == text[s+j] ) -- j;
59 if ( j < 0 ) occ.insert(s);
60 s += delta;
61 }
62 }
64 return occ;
65 }
66
67
68 } /* namespace exact */
69
70} /* namespace stringology */
71
Definition: set.hpp:44
Linear string.
Definition: LinearString.h:57
const ext::vector< SymbolType > & getContent() const &
Definition: LinearString.h:238
Definition: QuiteNaive.h:26
static ext::set< unsigned > match(const string::LinearString< SymbolType > &subject, const string::LinearString< SymbolType > &pattern)
Definition: QuiteNaive.h:38
void start(measurements::stealth_string name, measurements::Type type)
Definition: measurements.cpp:14
void end()
Definition: measurements.cpp:19
Definition: ArithmeticCompression.h:18