QuiteNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/measure>
 
#include <alib/set>
#include <alib/vector>
 
#include <string/LinearString.h>
 
 
namespace stringology {
 
    namespace exact {
 
 
        class QuiteNaive{
        public:
            template < class SymbolType >
            static ext::set < unsigned > match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern );
 
        };
 
        template < class SymbolType >
        ext::set < unsigned > QuiteNaive::match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
            ext::set<unsigned> occ;
            const auto & text = subject.getContent();
            const auto & pat = pattern.getContent();
            size_t n = text.size(), m = pat.size();
 
            measurements::start ( "Preprocess", measurements::Type::PREPROCESS );
            // Preprocessing
            size_t gamma = 1 , delta = 1 ;
            while ( delta < m && pat[m-1] != pat[m-1-delta]) ++ delta;
            while ( gamma < m && pat[m-1] == pat[m-1-gamma]) ++ gamma;
            measurements::end() ;
 
            measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
            // Searching
            size_t s = 0;
            while ( s <= n - m ){
                if ( pat[m-1] != text[s+m-1] ) s += gamma;
                else {
                    ssize_t j = m - 2;
                    while ( j >= 0 && pat[j] == text[s+j] ) -- j;
                    if ( j < 0 ) occ.insert(s);
                    s += delta;
                }
            }
            measurements::end() ;
            return occ;
        }
 
 
    } /* namespace exact */
 
} /* namespace stringology */