Dogaru.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 Dogaru{
        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 > Dogaru::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();
            long int n = text.size(), m = pat.size();
 
            unsigned i = 0 , j = 0 , k = 0 ;
 
            measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
            do {
                j = 0 ;
                while ( j < m && pat[j] == text[i] ) { ++ i ; ++ j ; }
                if ( j == m ) { occ.insert( i - j ) ; continue ; }
                one: ++ i ;
                while ( i <= n - m + j && pat[j] != text[i] ) ++ i ;
                if ( i > n - m + j ) { measurements::end() ; return occ ; }
                k = 0 ;
                while ( k <= m - 1 && pat[k] == text[ i - j + k ] ) ++ k ;
                if ( k == m ) { occ.insert( i - j ) ; i = i - j + m ; }
                else { goto one ;}
 
            } while ( i < n - m + j ) ;
 
            measurements::end() ;
            return occ;
        }
 
 
    } /* namespace exact */
 
} /* namespace stringology */