ReversedBoyerMooreHorspool.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
#include <alib/map>
 
#include <string/LinearString.h>
 
#include <string/properties/ReversedBadCharacterShiftTable.h>
 
namespace stringology {
 
namespace exact {
 
class ReversedBoyerMooreHorspool {
public:
    template < class SymbolType >
    static ext::set < unsigned > match ( const string::LinearString < SymbolType > & string, const string::LinearString < SymbolType > & pattern );
 
};
 
template < class SymbolType >
ext::set < unsigned > ReversedBoyerMooreHorspool::match ( const string::LinearString < SymbolType > & string, const string::LinearString < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::map < SymbolType, size_t > bcs = string::properties::ReversedBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
 
    if ( string.getContent ( ).size ( ) < pattern.getContent ( ).size ( ) )
        return occ;
 
     // index to the subject
    size_t i = string.getContent ( ).size ( ) - pattern.getContent ( ).size ( );
 
     // main loop of the algorithm over all possible indexes where the pattern can start
    while ( true ) {
        size_t j = 0;
 
        while ( j < pattern.getContent ( ).size ( ) && string.getContent ( ) [ i + j ] == pattern.getContent ( ) [ j ] )
            j++;
 
         // Yay, there is match!!!
        if ( j == pattern.getContent ( ).size ( ) ) occ.insert ( i );
 
         // shift heristics
        size_t shift = bcs [ string.getContent ( ) [ i ] ];
 
        if ( shift > i )
            break;
 
        i -= shift;
 
        // common::Streams::out << haystack_offset << std::endl;
    }
 
    return occ;
}
 
} /* namespace exact */
 
} /* namespace stringology */