ExactCoversComputation.h

Go to the documentation of this file.

 
#pragma once
 
#include <string/LinearString.h>
#include <automaton/FSM/NFA.h>
#include <stringology/indexing/NondeterministicExactSuffixAutomaton.h>
 
namespace stringology::cover {
 
class ExactCoversComputation {
public:
    template < class SymbolType >
    static ext::set < string::LinearString < SymbolType > > compute ( const string::LinearString < SymbolType > & pattern );
};
 
template < class SymbolType >
ext::set < string::LinearString < SymbolType > > ExactCoversComputation::compute ( const string::LinearString < SymbolType > & pattern ) {
 
    automaton::NFA < SymbolType, unsigned > suffixNDA = stringology::indexing::NondeterministicExactSuffixAutomaton::construct ( pattern );
 
    ext::set < unsigned > previousState ( { suffixNDA.getInitialState ( ) } );
    ext::vector < SymbolType > inputString = pattern.getContent ( );
 
    ext::set < string::LinearString < SymbolType > > result;
    ext::vector < SymbolType > cover;
 
    for ( const SymbolType & symbol : inputString ) {
        cover.push_back ( symbol );
 
        ext::set < unsigned > newState;
        for ( unsigned nfaState : previousState ) {
            auto transition_range = suffixNDA.getTransitions ( ).equal_range ( ext::make_pair ( nfaState, symbol ) );
            for ( const auto & it : transition_range ) {
                newState.insert ( it.second );
            }
        }
 
        previousState = newState;
 
        if ( newState.size ( ) < 2 )
            break;
 
        // if last element fulfills the condition (L17), then check all neighboring elements. We iterate backwards in order to save some iterator repositioning for the last element.
        if ( * newState.rbegin ( ) == inputString.size ( ) ) { // safe (at least 2 elements)
            bool isCover = true;
            auto it = std::next ( newState.rbegin ( ) );
            auto prev = newState.rbegin ( );
 
            for ( ; it != newState.rend ( ); ++ it, ++ prev ) {
                if ( *prev - *it > cover.size ( ) ) {
                    isCover = false;
                    break;
                }
            }
 
            if ( isCover )
                result.insert ( string::LinearString < SymbolType > ( cover ) );
        }
    }
 
    return result;
}
 
} /* namespace stringology::cover */