NaiveDAWGMatcherConstruction.h

Go to the documentation of this file.

 
/*
 * Author: Radovan Cerveny
 */
 
#pragma once
 
#include <automaton/FSM/DFA.h>
#include <string/LinearString.h>
 
#include <automaton/determinize/Determinize.h>
#include <automaton/simplify/Minimize.h>
#include <automaton/simplify/Rename.h>
#include <automaton/simplify/EpsilonRemoverIncoming.h>
#include <stringology/indexing/NondeterministicExactSuffixEpsilonAutomaton.h>
#include <stringology/indexing/ExactSuffixAutomaton.h>
 
namespace stringology {
 
namespace matching {
 
class NaiveDAWGMatcherConstruction {
public:
    template < class SymbolType >
    static indexes::stringology::SuffixAutomaton < SymbolType > naiveConstruct ( const string::LinearString < SymbolType > & pattern );
 
};
 
template < class SymbolType >
indexes::stringology::SuffixAutomaton < SymbolType > NaiveDAWGMatcherConstruction::naiveConstruct ( const string::LinearString < SymbolType > & pattern ) {
    auto patternData = pattern.getContent ( );
    reverse ( patternData.begin ( ), patternData.end ( ) );
    string::LinearString < SymbolType > reversedPattern ( pattern.getAlphabet ( ), std::move ( patternData ) );
 
    automaton::EpsilonNFA < SymbolType, unsigned > nfaSuffixAutomaton = stringology::indexing::NondeterministicExactSuffixEpsilonAutomaton::construct ( reversedPattern );
    automaton::DFA < SymbolType, unsigned > res = automaton::simplify::Rename::rename ( automaton::simplify::Minimize::minimize ( automaton::determinize::Determinize::determinize ( automaton::simplify::EpsilonRemoverIncoming::remove ( nfaSuffixAutomaton ) ) ) );
 
    return indexes::stringology::SuffixAutomaton < SymbolType > ( std::move ( res ), pattern.getContent ( ).size ( ) );
}
 
} /* namespace matching */
 
} /* namespace stringology */