SuffixAutomatonFactors.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/SuffixAutomaton.h>
#include <string/LinearString.h>
 
#include <automaton/run/Run.h>
#
 
namespace stringology {
 
namespace query {
 
class SuffixAutomatonFactors {
public:
    template < class SymbolType >
    static ext::set < unsigned > query ( const indexes::stringology::SuffixAutomaton < SymbolType > & suffixAutomaton, const string::LinearString < SymbolType > & string );
};
 
template < class SymbolType >
ext::set < unsigned > SuffixAutomatonFactors::query ( const indexes::stringology::SuffixAutomaton < SymbolType > & suffixAutomaton, const string::LinearString < SymbolType > & string ) {
    unsigned backboneLength = suffixAutomaton.getBackboneLength ( );
 
    ext::tuple < bool, unsigned, ext::set < unsigned > > run = automaton::run::Run::calculateState ( suffixAutomaton.getAutomaton ( ), string );
    if ( ! std::get < 0 > ( run ) )
        return { };
 
    std::deque < std::pair < unsigned, unsigned > > open = { { std::get < 1 > ( run ), 0u } };
    ext::vector < unsigned > tmp;
    while ( ! open.empty ( ) ) {
        std::pair < unsigned, unsigned > cur = std::move ( open.back ( ) );
        open.pop_back ( );
 
        if ( suffixAutomaton.getAutomaton ( ).getFinalStates ( ).count ( cur.first ) )
            tmp.push_back ( cur.second );
 
        for ( const auto & transition : suffixAutomaton.getAutomaton ( ).getTransitionsFromState ( cur.first ) )
            open.emplace_back ( transition.second, cur.second + 1 );
    }
 
    ext::set < unsigned > res;
    for ( unsigned dist : tmp )
        res.insert ( backboneLength - dist - string.getContent ( ).size ( ) );
 
    return res;
}
 
} /* namespace query */
 
} /* namespace stringology */