NondeterministicApproximateSuffixEpsilonAutomatonForHammingDistance.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <string/LinearString.h>
 
namespace stringology::indexing {
 
class NondeterministicApproximateSuffixEpsilonAutomatonForHammingDistance {
public:
    template < class SymbolType >
    static automaton::EpsilonNFA < SymbolType, ext::pair < unsigned int, unsigned int > > construct ( const string::LinearString < SymbolType > & pattern, unsigned int k );
};
 
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, ext::pair < unsigned int, unsigned int > > NondeterministicApproximateSuffixEpsilonAutomatonForHammingDistance::construct ( const string::LinearString < SymbolType > & pattern, unsigned int k ) {
    auto initial_state = ext::make_pair ( 0, 0 );
 
    automaton::EpsilonNFA < SymbolType, ext::pair < unsigned int, unsigned int > > result ( initial_state );
    result.setInputAlphabet( pattern.getAlphabet ( ) );
 
    for ( unsigned int j = 0; j < k + 1; j ++ ) {
        for ( unsigned int i = j ; i < pattern.getContent ( ).size ( ) + 1 ; i++ ) {
            result.addState ( ext::make_pair ( i, j ) );
            if ( i == pattern.getContent ( ).size ( ) ) {
                result.addFinalState ( ext::make_pair ( i, j ) );
            }
        }
    }
 
    for ( unsigned int j = 0 ; j < k + 1 ; j ++ ) {
        for ( unsigned int i = j; i < pattern.getContent ( ).size ( ); i ++ ) {
            auto from = ext::make_pair ( i, j );
            auto to = ext::make_pair ( i + 1, j );
            result.addTransition ( from, pattern.getContent ( ) [ i ], to );
        }
    }
 
    for ( unsigned int j = 0 ; j < k ; j ++ ) {
        for ( unsigned int i = j ; i < pattern.getContent ( ).size ( ); i ++ ) {
            auto from = ext::make_pair ( i, j );
            auto to = ext::make_pair ( i + 1, j + 1 );
 
            for ( const SymbolType & symbol : pattern.getAlphabet ( ) ) {
                if ( symbol != pattern.getContent ( ) [ i ] ) {
                    result.addTransition ( from, symbol, to );
                }
            }
        }
    }
 
    //epsilon transitions
    for ( unsigned int j = 1 ; j <= pattern.getContent ( ).size ( ); j ++ ) {
        auto from =  ext::make_pair ( 0, 0 );
        auto to = ext::make_pair ( j, 0 );
        result.addTransition ( from, to );
    }
 
    return result;
}
 
} /* namespace stringology::indexing */