WideBNDMOccurrences.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/BitParallelIndex.h>
#include <string/LinearString.h>
#include <global/GlobalData.h>
 
#include <ext/foreach>
 
namespace stringology {
 
namespace query {
 
class WideBNDMOccurrences {
public:
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::stringology::BitParallelIndex < SymbolType > & pattern, const string::LinearString < SymbolType > & subject );
 
};
 
template < class SymbolType >
ext::set < unsigned > WideBNDMOccurrences::query ( const indexes::stringology::BitParallelIndex < SymbolType > & pattern, const string::LinearString < SymbolType > & subject ) {
 
    ext::set < unsigned > occ;
 
    size_t patternLength = pattern.getData ( ).begin ( )->second.size ( );
    size_t subjectLength = subject.getContent ( ).size ( );
    size_t posInSubject = 0;
 
    ext::vector < bool > currentBitmask;
    currentBitmask.resize ( patternLength );
 
    while ( posInSubject + patternLength <= subjectLength ) {
        size_t posInPattern = patternLength;
        size_t lastPosOfFactor = patternLength;
 
         // Set the bitmask to all ones
        ext::fill ( currentBitmask );
 
        while ( posInPattern > 0 && ext::any ( currentBitmask ) ) {
            typename ext::map < SymbolType, ext::vector < bool > >::const_iterator symbolVectorIter = pattern.getData ( ).find ( subject.getContent ( ).at ( posInSubject + posInPattern - 1 ) );
            if ( symbolVectorIter == pattern.getData ( ).end ( ) )
                break;
 
            currentBitmask &= symbolVectorIter->second;
            posInPattern--;
 
             // Test whether the most significant bit is set
            if ( currentBitmask [ patternLength - 1 ] ) {
                 // and we didn't process all symbols of the pattern
                if ( posInPattern > 0 )
                    lastPosOfFactor = posInPattern;
                else /* posInPattern == 0 */
                     // Yay, there is match!!!
                    occ.insert ( posInSubject );
            }
 
            currentBitmask <<= 1;
        }
 
        posInSubject += lastPosOfFactor;
    }
 
    return occ;
}
 
} /* namespace query */
 
} /* namespace stringology */