ApproximateEnhancedCoversComputation.h

Go to the documentation of this file.

 
#pragma once
 
#include <stringology/cover/ApproximateEnhancedCoversCommon.h>
 
namespace stringology::cover {
class ApproximateEnhancedCoversComputation : ApproximateEnhancedCoversCommon {
public:
    template < class SymbolType >
    static ext::set < string::LinearString < SymbolType > > compute ( const string::LinearString < SymbolType > & x, unsigned k );
};
 
template < class SymbolType >
ext::set < string::LinearString < SymbolType > > ApproximateEnhancedCoversComputation::compute ( const string::LinearString < SymbolType > & x, unsigned k ) {
     // found approximate enhanced covers are not stored directly but rather as a
     // set of lfactors
    ext::set < ext::pair < unsigned, unsigned > > result;
 
     // the maximum number of covered positions
    unsigned h = 0;
 
     // there are no borders for an empty string and a string with only one
     // character
    if ( x.getContent ( ).size ( ) < 2 )
        return ext::set < string::LinearString < SymbolType > >( );
 
    State previousState = constrFirstState ( x, k, x.getContent ( )[0] );
 
     // check if the first character is a border (makes sense only for k = 0)
    if ( isBorder ( previousState, x, k ) )
        updateEnhCov ( previousState, result, h );
 
    for ( size_t i = 1; i < x.getContent ( ).size ( ); ++i ) {
        State nextState = constrNextState ( x, previousState, k, x.getContent ( )[previousState.depth] );
 
        if ( nextState.elements.size ( ) < 2 )
            break;
 
        if ( isBorder ( nextState, x, k ) )
            updateEnhCov ( nextState, result, h );
 
        previousState = std::move ( nextState );
    }
 
     // in the end the set of actual strings is computed from the set of lfactors
    return getFactors ( x, result );
}
 
} /* namespace stringology::cover */