SequenceMatchingAutomaton.h

Go to the documentation of this file.

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