ExactSubsequenceAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <automaton/FSM/DFA.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace indexing {
 
class ExactSubsequenceAutomaton {
public:
    template < class SymbolType >
    static automaton::DFA < SymbolType, unsigned > construct ( const string::LinearString < SymbolType > & text );
};
 
template < class SymbolType >
automaton::DFA < SymbolType, unsigned > ExactSubsequenceAutomaton::construct ( const string::LinearString < SymbolType > & text ) {
    ext::map < SymbolType, unsigned > f;
    for(const SymbolType & symbol : text.getAlphabet ( ) ) {
        f[symbol] = 0;
    }
 
    automaton::DFA < SymbolType, unsigned > res ( 0 );
    res.addFinalState ( 0 );
    res.setInputAlphabet ( text.getAlphabet ( ) );
 
    unsigned i = 1;
    for ( const SymbolType & symbol : text.getContent ( ) ) {
        res.addState ( i );
        res.addFinalState ( i );
 
        for ( unsigned j = f [ symbol ]; j < i; j++ ) {
            res.addTransition ( j, symbol, i );
        }
        f[symbol] = i;
        i++;
    }
 
    return res;
}
 
} /* namespace indexing */
 
} /* namespace stringology */