RelaxedApproximateEnhancedCoversComputation.h

Go to the documentation of this file.

 
#pragma once
 
#include <stringology/cover/ApproximateEnhancedCoversCommon.h>
 
namespace stringology::cover {
 
class RelaxedApproximateEnhancedCoversComputation : ApproximateEnhancedCoversCommon {
public:
    template < class SymbolType >
    static ext::set < string::LinearString < SymbolType > > compute ( const string::LinearString < SymbolType > & x, unsigned k );
 
private:
    template < class SymbolType >
    static void processState ( const string::LinearString < SymbolType > & x, unsigned k, const State & previousState, ext::set < ext::pair < unsigned, unsigned > > & covers, unsigned & h );
};
 
template < class SymbolType >
ext::set < string::LinearString < SymbolType > > RelaxedApproximateEnhancedCoversComputation::compute ( const string::LinearString < SymbolType > & x, unsigned k ) {
     // found relaxed approximate enhanced covers are not stored directly but
     // rather as a set of lfactors
    ext::set < ext::pair < unsigned, unsigned > > result;
    unsigned h = 0;
 
    if ( x.getContent ( ).size ( ) < 2 )
        return ext::set < string::LinearString < SymbolType > >( );
 
    for ( const auto & symbol : x.getAlphabet ( ) ) {
        State firstState = constrFirstState ( x, k, symbol );
 
         // check if the first character is a border (makes sense only for k = 0)
        if ( isBorder ( firstState, x, k ) )
            updateEnhCov ( firstState, result, h );
 
        processState ( x, k, firstState, result, h );
    }
 
     // in the end the set of actual strings is computed from the set of lfactors
    return getFactors ( x, result );
}
 
template < class SymbolType >
void RelaxedApproximateEnhancedCoversComputation::processState ( const string::LinearString < SymbolType > & x, unsigned k, const State & previousState, ext::set < ext::pair < unsigned, unsigned > > & covers, unsigned & h ) {
    for ( const auto & symbol : x.getAlphabet ( ) ) {
        State currState = constrNextState ( x, previousState, k, symbol );
        bool isFactor = false;
 
        for ( const Element & element : currState.elements )
            if ( element.level == 0 ) {
                currState.lfactor = ext::pair < unsigned, unsigned > ( element.depth, currState.depth );
                isFactor = true;
            }
 
        if ( ( currState.elements.size ( ) > 1 ) && ( ( currState.elements[0].depth == currState.depth ) && isFactor ) ) {
            if ( ( currState.elements[currState.elements.size ( ) - 1].depth == x.getContent ( ).size ( ) ) && ( currState.depth > k ) )
                updateEnhCov ( currState, covers, h );
 
            processState ( x, k, currState, covers, h );
        }
    }
}
 
} // namespace stringology::cover