BoyerMoore.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/set>
#include <alib/map>
#include <alib/measure>
 
#include <string/LinearString.h>
 
#include <string/properties/BadCharacterShiftTable.h>
#include <string/properties/GoodSuffixShiftTable.h>
 
#include <global/GlobalData.h>
 
namespace stringology {
 
namespace exact {
 
class BoyerMoore {
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> BoyerMoore::match(const string::LinearString < SymbolType >& string, const string::LinearString < SymbolType >& pattern) {
    ext::set<unsigned> occ;
 
    measurements::start ( "Preprocess", measurements::Type::PREPROCESS );
    ext::map<SymbolType, size_t> bcs = string::properties::BadCharacterShiftTable::bcs(pattern); //NOTE: the subjects alphabet must be a subset or equal to the pattern
    ext::vector<size_t> gss = string::properties::GoodSuffixShiftTable::gss(pattern);
    measurements::end ( );
 
    if(common::GlobalData::verbose) {
        common::Streams::log << "bcs = " << bcs << std::endl;
        common::Streams::log << "gss = " << gss << std::endl;
    }
 
    measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
    size_t haystack_offset = 0;
    while(haystack_offset + pattern.getContent().size() <= string.getContent().size()) {
        size_t i = pattern.getContent().size();
        while(i > 0 && string.getContent()[haystack_offset + i - 1] == pattern.getContent()[i - 1]) {
            i--;
        }
 
        // Yay, there is match!!!
        if(i == 0) occ.insert(haystack_offset);
        haystack_offset += std::max ( bcs[string.getContent()[haystack_offset + pattern.getContent().size() - 1]], gss [ pattern.getContent ( ).size ( ) - i ] );
        //common::Streams::out << haystack_offset << std::endl;
    }
    measurements::end ( );
 
    return occ;
}
 
} /* namespace exact */
 
} /* namespace stringology */