ExactFactorOracleAutomaton.h

Go to the documentation of this file.

 
/*
 * Author: Radovan Cerveny
 */
 
#pragma once
 
#include <limits>
 
#include <indexes/stringology/FactorOracleAutomaton.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace indexing {
 
class ExactFactorOracleAutomaton {
private:
    static constexpr unsigned infinity = std::numeric_limits < unsigned >::max ( );
 
    template < class SymbolType >
    static void oracleAddLetter ( automaton::DFA < SymbolType, unsigned > & oracle, const SymbolType & symbol, ext::vector < unsigned > & supplyFunction );
 
public:
    template < class SymbolType >
    static indexes::stringology::FactorOracleAutomaton < SymbolType > construct ( const string::LinearString < SymbolType > & pattern );
 
};
 
template < class SymbolType >
indexes::stringology::FactorOracleAutomaton < SymbolType > ExactFactorOracleAutomaton::construct ( const string::LinearString < SymbolType > & pattern ) {
    automaton::DFA < SymbolType, unsigned > oracleAutomaton ( 0u );
 
    oracleAutomaton.addFinalState ( oracleAutomaton.getInitialState ( ) );
 
    ext::vector < unsigned > supplyFunction { infinity }; //vector is fine, the state number is exactly the index to the vector
 
    oracleAutomaton.setInputAlphabet ( pattern.getAlphabet ( ) );
 
    for ( const SymbolType & symbol : pattern.getContent ( ) )
        oracleAddLetter ( oracleAutomaton, symbol, supplyFunction );
 
    return indexes::stringology::FactorOracleAutomaton < SymbolType > ( std::move ( oracleAutomaton ) );
}
 
template < class SymbolType >
void ExactFactorOracleAutomaton::oracleAddLetter ( automaton::DFA < SymbolType, unsigned > & oracle, const SymbolType & symbol, ext::vector < unsigned > & supplyFunction ) {
    unsigned lastState = oracle.getStates ( ).size ( ) - 1;
    unsigned newState = lastState + 1;
 
    oracle.addState ( newState );
    oracle.addFinalState ( newState );
 
    oracle.addTransition ( lastState, symbol, newState );
    unsigned kState = supplyFunction.at ( lastState );
 
    while ( kState != infinity && oracle.getTransitions ( ).find ( { kState, symbol } ) == oracle.getTransitions ( ).end ( ) ) {
        oracle.addTransition ( kState, symbol, newState );
        kState = supplyFunction.at ( kState );
    }
 
    unsigned supplyState = 0;
 
    if ( kState != infinity )
        supplyState = oracle.getTransitions ( ).find( { kState, symbol } )->second;
 
    supplyFunction.push_back ( supplyState );
}
 
} /* namespace indexing */
 
} /* namespace stringology */