DeadZoneUsingBadCharacterShift.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
#include <alib/map>
 
#include <string/LinearString.h>
 
#include <string/properties/BadCharacterShiftTable.h>
#include <string/properties/ReversedBadCharacterShiftTable.h>
 
namespace stringology {
 
namespace exact {
 
class DeadZoneUsingBadCharacterShift {
    template < class SymbolType >
    static void match_rec ( ext::set < unsigned > & occ, const string::LinearString < SymbolType > & string, const string::LinearString < SymbolType > & pattern, ext::map < SymbolType, size_t > & fbcs, ext::map < SymbolType, size_t > & bbcs, int low, int high );
 
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 > DeadZoneUsingBadCharacterShift::match ( const string::LinearString < SymbolType > & string, const string::LinearString < SymbolType > & pattern ) {
    ext::set < unsigned > occ;
    ext::map < SymbolType, size_t > fbcs = string::properties::BadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
    ext::map < SymbolType, size_t > bbcs = string::properties::ReversedBadCharacterShiftTable::bcs ( pattern ); // NOTE: the subjects alphabet must be a subset or equal to the pattern
 
    match_rec ( occ, string, pattern, fbcs, bbcs, 0, string.getContent ( ).size ( ) - pattern.getContent ( ).size ( ) + 1 );
    return occ;
}
 
template < class SymbolType >
void DeadZoneUsingBadCharacterShift::match_rec ( ext::set < unsigned > & occ, const string::LinearString < SymbolType > & string, const string::LinearString < SymbolType > & pattern, ext::map < SymbolType, size_t > & fbcs, ext::map < SymbolType, size_t > & bbcs, int low, int high ) {
    if ( low >= high ) return;
 
    int middle = ( low + high ) / 2;
    size_t i = 0;
 
    while ( i < pattern.getContent ( ).size ( ) && string.getContent ( )[middle + i] == pattern.getContent ( )[i] )
        i++;
 
     // Yay, there is match!!!
    if ( i == pattern.getContent ( ).size ( ) ) occ.insert ( middle );
 
    match_rec ( occ, string, pattern, fbcs, bbcs, low, middle - bbcs[string.getContent ( )[middle]] + 1 );
    match_rec ( occ, string, pattern, fbcs, bbcs, middle + fbcs[string.getContent ( )[middle + pattern.getContent ( ).size ( ) - 1]], high );
}
 
} /* namespace exact */
 
} /* namespace stringology */