BackwardDAWGMatching.h

Go to the documentation of this file.

 
/*
 * Author: Radovan Cerveny
 */
 
#pragma once
 
#include <alib/set>
 
#include <indexes/stringology/SuffixAutomaton.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace query {
 
class BackwardDAWGMatching {
public:
    template < class SymbolType >
    static ext::set < unsigned > match ( const string::LinearString < SymbolType > & subject, const indexes::stringology::SuffixAutomaton < SymbolType > & suffixAutomaton );
 
};
 
template < class SymbolType >
ext::set < unsigned > BackwardDAWGMatching::match ( const string::LinearString < SymbolType > & subject, const indexes::stringology::SuffixAutomaton < SymbolType > & suffixAutomaton ) {
    ext::set < unsigned > occ;
 
    size_t patternSize = suffixAutomaton.getBackboneLength ( );
    size_t subjectSize = subject.getContent ( ).size ( );
 
    bool fail;
    size_t posInSubject = 0;
 
    while ( posInSubject + patternSize <= subjectSize ) {
        unsigned currentState = suffixAutomaton.getAutomaton ( ).getInitialState ( );
 
        size_t posInPattern = patternSize;
        size_t lastPrefixPos = posInPattern;
 
        fail = false;
        while ( posInPattern > 0 && ! fail ) {
            auto transition = suffixAutomaton.getAutomaton ( ).getTransitions ( ).find ( { currentState, subject.getContent ( ).at ( posInSubject + posInPattern - 1 ) } );
 
            if ( transition == suffixAutomaton.getAutomaton ( ).getTransitions ( ).end ( ) )
                fail = true;
            else
                currentState = transition->second;
 
            posInPattern--;
 
             // found a prefix of nonreversed pattern that does not correspond to the entire pattern
            if ( ( posInPattern != 0 ) && ( suffixAutomaton.getAutomaton ( ).getFinalStates ( ).find ( currentState ) != suffixAutomaton.getAutomaton ( ).getFinalStates ( ).end ( ) ) )
                lastPrefixPos = posInPattern;
        }
 
        if ( ! fail )
             // Yay, there is match!!!
            occ.insert ( posInSubject );
 
        posInSubject += lastPrefixPos;
    }
 
    return occ;
}
 
} /* namespace query */
 
} /* namespace stringology */