DeterministicApproximateSuffixAutomatonForHammingDistanceFactory.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/DFA.h>
#include <string/LinearString.h>
#include <stringology/indexing/NondeterministicApproximateSuffixAutomatonForHammingDistance.h>
#include <stack>
 
namespace stringology::seed
{
class DeterministicApproximateSuffixAutomatonForHammingDistanceFactory
{
private:
    using StateType = ext::set < ext::pair < unsigned, unsigned > >;
 
    template<class SymbolType>
    static void processState( const StateType & node, automaton::DFA < SymbolType, StateType > & result,
                             const automaton::NFA < SymbolType, ext::pair < unsigned, unsigned > > & ndSuffixAutomaton,
                             std::stack < StateType > & stack )
    {
        for ( const auto & symb : result.getInputAlphabet() )
        {
            StateType newNode;
            for ( const auto & n : node )
            {
                auto transitionsOnSymb = ndSuffixAutomaton.getTransitions ( ).equal_range( ext::make_pair( n, symb ) );
                for ( const auto & it : transitionsOnSymb )
                    newNode.insert( it.second );
            }
            if ( ! newNode.empty() )
            {
                result.addState( newNode );
                result.addTransition( node, symb, newNode );
                stack.push( newNode );
            }
        }
    }
 
public:
    template<class SymbolType>
    static automaton::DFA < SymbolType, StateType > construct( const string::LinearString < SymbolType > & pattern, unsigned k )
    {
        auto ndSuffixAutomaton = stringology::indexing::NondeterministicApproximateSuffixAutomatonForHammingDistance::construct( pattern, k );
 
        /* automaton creation */
        StateType initialState;
        initialState.insert( ext::pair < unsigned, unsigned >( 0, 0 ) );
        automaton::DFA < SymbolType, StateType > result( initialState );
        result.setInputAlphabet( pattern.getAlphabet() );
 
        /* stack initialization */
        std::stack < StateType > stack;
        stack.push( initialState );
 
        /* visiting the nodes, adding states, transitions, finalStates */
        while ( ! stack.empty() )
        {
            auto node = stack.top();
            stack.pop();
 
            if ( std::any_of( node.begin(), node.end(), [&] ( auto x ) { return ndSuffixAutomaton.getFinalStates().find( x ) != ndSuffixAutomaton.getFinalStates().end(); } ) )
                result.addFinalState( node );
 
            processState( node, result, ndSuffixAutomaton, stack );
        }
        return result;
    }
};
}