NondeterministicApproximateSuffixAutomatonForHammingDistance.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/NFA.h>
#include <string/LinearString.h>
 
namespace stringology::indexing {
 
class NondeterministicApproximateSuffixAutomatonForHammingDistance {
public:
    template < class SymbolType >
    static automaton::NFA < SymbolType, ext::pair < unsigned int, unsigned int > > construct ( const string::LinearString < SymbolType > & pattern, unsigned int k );
};
 
template < class SymbolType >
automaton::NFA < SymbolType, ext::pair < unsigned int, unsigned int > > NondeterministicApproximateSuffixAutomatonForHammingDistance::construct ( const string::LinearString < SymbolType > & pattern, unsigned int k ) {
    automaton::NFA < SymbolType, ext::pair < unsigned int, unsigned int > > result ( ext::make_pair ( 0, 0 ) );
    result.addFinalState ( result.getInitialState ( ) );
    result.setInputAlphabet( pattern.getAlphabet ( ) );
 
    // create states
    for ( size_t j = 0; j <= k; j ++ ) {
        for ( size_t i = j ; i <= pattern.getContent ( ).size ( ) ; i++ ) {
            result.addState ( ext::make_pair ( i, j ) );
 
            if ( i == pattern.getContent ( ).size ( ) )
                result.addFinalState ( ext::make_pair ( pattern.getContent ( ).size ( ), j ) );
        }
 
    }
 
    // horizontal transitions
    for ( size_t j = 0 ; j <= k ; j ++ ) {
        for ( size_t 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 );
        }
    }
 
    // diagonal transitions
    for ( size_t j = 0 ; j < k ; j ++ ) {
        for ( size_t 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 );
                }
            }
        }
    }
 
    // removed epsilon transitions
    for ( unsigned int i = 1 ; i < pattern.getContent ( ).size ( ); i ++ ) {
        auto from = ext::make_pair ( 0, 0 );
        result.addTransition ( from, pattern.getContent ( ) [ i ], ext::make_pair ( i + 1, 0 ) );
 
        if ( k > 0 ) {
            for ( const SymbolType & symbol : pattern.getAlphabet ( ) ) {
                if ( symbol != pattern.getContent ( ) [ i ] ) {
                    result.addTransition ( from, symbol, ext::make_pair ( i + 1, 1 ) );
                }
            }
        }
    }
 
    return result;
}
 
} /* namespace stringology::indexing */