ExactMultiNondeterministicSubsequenceAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/EpsilonNFA.h>
#include <string/LinearString.h>
 
#include <alib/pair>
 
namespace stringology {
 
namespace indexing {
 
class ExactMultiNondeterministicSubsequenceAutomaton {
public:
    template < class SymbolType >
    static automaton::EpsilonNFA < SymbolType, ext::pair < unsigned, unsigned > > construct ( const ext::set < string::LinearString < SymbolType > > & texts);
};
 
template < class SymbolType >
automaton::EpsilonNFA < SymbolType, ext::pair < unsigned, unsigned > > ExactMultiNondeterministicSubsequenceAutomaton::construct ( const ext::set < string::LinearString < SymbolType > > & texts) {
    automaton::EpsilonNFA < SymbolType, ext::pair < unsigned, unsigned > > res ( ext::make_pair ( 0u, 0u ) );
    res.addFinalState ( ext::make_pair ( 0u, 0u ) );
 
    unsigned j = 1;
    for ( const string::LinearString < SymbolType > & text : texts ) {
        res.addInputSymbols ( text.getAlphabet ( ) );
 
        res.addState ( ext::make_pair ( 0u, j ) );
        res.addFinalState ( ext::make_pair ( 0u, j ) );
        res.addTransition ( ext::make_pair ( 0u, 0u ), ext::make_pair ( 0u, j ) );
 
        unsigned i = 1;
        for ( const SymbolType & symbol : text.getContent ( ) ) {
            res.addState ( ext::make_pair ( i, j ) );
            res.addFinalState ( ext::make_pair ( i, j ) );
 
            res.addTransition ( ext::make_pair ( i - 1, j ), symbol, ext::make_pair ( i, j ) );
            res.addTransition ( ext::make_pair ( i - 1, j ), ext::make_pair ( i, j ) );
            i++;
        }
        j++;
    }
 
    return res;
}
 
} /* namespace indexing */
 
} /* namespace stringology */