ExactSuffixAutomaton.h

Go to the documentation of this file.

 
/*
 * Author: Radovan Cerveny
 */
 
#pragma once
 
#include <limits>
 
#include <indexes/stringology/SuffixAutomaton.h>
#include <string/LinearString.h>
 
#include <global/GlobalData.h>
 
namespace stringology {
 
namespace indexing {
 
class ExactSuffixAutomaton {
private:
    static constexpr unsigned infinity = std::numeric_limits < unsigned >::max ( );
 
    template < class SymbolType >
    static void suffixAutomatonAddSymbol ( automaton::DFA < SymbolType, unsigned > & suffixAutomaton, const SymbolType & symbol, std::vector < std::pair < unsigned, int > > & suffixLinks, unsigned & lastState );
 
public:
    template < class SymbolType >
    static indexes::stringology::SuffixAutomaton < SymbolType > construct ( const string::LinearString < SymbolType > & pattern );
 
};
 
template < class SymbolType >
indexes::stringology::SuffixAutomaton < SymbolType > ExactSuffixAutomaton::construct ( const string::LinearString < SymbolType > & pattern ) {
    automaton::DFA < SymbolType, unsigned > suffixAutomaton ( 0 );
 
    suffixAutomaton.setInputAlphabet ( pattern.getAlphabet ( ) );
 
    std::vector < std::pair < unsigned, int > > suffixLinks = { { infinity, 0 } }; //vector is fine, the state number is exactly the index to the vector
    unsigned lastState = 0;
 
    if ( common::GlobalData::verbose )
        common::Streams::log << "String size " << pattern.getContent ( ).size ( ) << std::endl;
 
    for ( const SymbolType & symbol : pattern.getContent ( ) ) {
        if ( common::GlobalData::verbose && lastState % 1000 == 0 )
            common::Streams::log << "Progress " << lastState << std::endl;
 
        suffixAutomatonAddSymbol ( suffixAutomaton, symbol, suffixLinks, lastState );
    }
 
    while ( lastState != infinity ) {
        suffixAutomaton.addFinalState ( lastState );
        lastState = suffixLinks [ lastState ].first;
    }
 
    return indexes::stringology::SuffixAutomaton < SymbolType > ( std::move ( suffixAutomaton ), pattern.getContent ( ).size ( ) );
}
 
template < class SymbolType >
void ExactSuffixAutomaton::suffixAutomatonAddSymbol ( automaton::DFA < SymbolType, unsigned > & suffixAutomaton, const SymbolType & symbol, std::vector < std::pair < unsigned, int > > & suffixLinks, unsigned & lastState ) {
    unsigned newState = suffixAutomaton.getStates ( ).size ( );
 
    suffixAutomaton.addState ( newState );
 
    int lastSuffixLength = suffixLinks [ lastState ].second;
 
    suffixLinks.emplace_back ( infinity, lastSuffixLength + 1 );
 
    unsigned kState = lastState;
 
    while ( kState != infinity && suffixAutomaton.getTransitions ( ).find ( { kState, symbol } ) == suffixAutomaton.getTransitions ( ).end ( ) ) {
        suffixAutomaton.addTransition ( kState, symbol, newState );
        kState = suffixLinks [ kState ].first;
    }
 
    if ( kState == infinity ) {
        suffixLinks [ newState ].first = 0;
    } else {
        unsigned qState = suffixAutomaton.getTransitions ( ).find ( { kState, symbol } )->second;
 
        int kSuffixLength = suffixLinks [ kState ].second;
        int qSuffixLength = suffixLinks [ qState ].second;
 
        if ( kSuffixLength + 1 == qSuffixLength ) {
            suffixLinks [ newState ].first = qState;
        } else {
            unsigned cloneState = suffixAutomaton.getStates ( ).size ( );
            suffixAutomaton.addState ( cloneState );
 
            suffixLinks.emplace_back ( suffixLinks [ qState ].first, kSuffixLength + 1 );
 
            for ( const auto & transition : suffixAutomaton.getTransitionsFromState ( qState ) )
                suffixAutomaton.addTransition ( cloneState, transition.first.second, transition.second );
 
            while ( kState != infinity && suffixAutomaton.removeTransition ( kState, symbol, qState ) ) {
                suffixAutomaton.addTransition ( kState, symbol, cloneState );
                kState = suffixLinks [ kState ].first;
            }
 
            suffixLinks [ qState ].first = cloneState;
            suffixLinks [ newState ].first = cloneState;
        }
    }
    lastState = newState;
}
 
} /* namespace indexing */
 
} /* namespace stringology */