NondeterministicExactSuffixAutomaton.h

Go to the documentation of this file.

 
/*
 * Author: Radovan Cerveny
 */
 
#pragma once
 
#include <automaton/FSM/NFA.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace indexing {
 
class NondeterministicExactSuffixAutomaton {
public:
    template < class SymbolType >
    static automaton::NFA < SymbolType, unsigned > construct ( const string::LinearString < SymbolType > & pattern );
 
};
 
template < class SymbolType >
automaton::NFA < SymbolType, unsigned > NondeterministicExactSuffixAutomaton::construct ( const string::LinearString < SymbolType > & pattern ) {
    automaton::NFA < SymbolType, unsigned > nfaSuffixAutomaton ( 0 );
 
    nfaSuffixAutomaton.setInputAlphabet ( pattern.getAlphabet ( ) );
 
    unsigned i = 0;
    for ( const SymbolType & symbol : pattern.getContent ( ) ) {
        nfaSuffixAutomaton.addState ( ++ i );
        nfaSuffixAutomaton.addTransition ( i - 1, symbol, i );
        nfaSuffixAutomaton.addTransition ( 0, symbol, i );
    }
 
    nfaSuffixAutomaton.setFinalStates ( { 0, i } );
 
    return nfaSuffixAutomaton;
}
 
} /* namespace indexing */
 
} /* namespace stringology */