KnuthMorrisPratt.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/measure>
 
#include <alib/set>
#include <alib/vector>
 
#include <string/properties/BorderArray.h>
 
#include <string/LinearString.h>
 
namespace stringology {
 
namespace exact {
 
class KnuthMorrisPratt {
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 > KnuthMorrisPratt::match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::vector < size_t > ba = string::properties::BorderArray::construct ( pattern );
 
    //measurements::start("Algorithm", measurements::Type::MAIN);
 
     // index to the subject
    unsigned i = 0;
    size_t j = 0;
 
     // main loop of the algorithm over all possible indexes where the pattern can start
    while ( i + pattern.getContent ( ).size ( ) <= subject.getContent ( ).size ( ) ) {
         // index to the pattern
 
        while ( j < pattern.getContent ( ).size ( ) && subject.getContent ( )[i + j] == pattern.getContent ( )[j] )
            j++;
 
         // match was found
        if ( j >= pattern.getContent ( ).size ( ) ) occ.insert ( i );
 
         // shift heristics
        if ( j != 0 ) {
            i += j - ba[j];
            j = ba[j];
        } else {
            i += 1;
        }
    }
 
    //measurements::end();
 
    return occ;
}
 
} /* namespace exact */
 
} /* namespace stringology */