GoodSuffixShiftTable.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
 
#include <string/LinearString.h>
 
#include <string/properties/BorderArray.h>
#include <automaton/determinize/Determinize.h>
#include <automaton/simplify/EpsilonRemoverIncoming.h>
#include <stringology/indexing/NondeterministicExactFactorAutomaton.h>
#include <string/transform/StringReverse.h>
 
namespace string {
 
namespace properties {
 
class GoodSuffixShiftTable {
public:
    template < class SymbolType >
    static ext::vector < size_t > gss ( const string::LinearString < SymbolType > & pattern );
 
};
 
template < class SymbolType >
ext::vector < size_t > GoodSuffixShiftTable::gss ( const string::LinearString < SymbolType > & pattern ) {
    string::LinearString < SymbolType > reversed = string::transform::StringReverse::reverse ( pattern );
 
    ext::vector < size_t > borderArray = string::properties::BorderArray::construct ( reversed );
    size_t max = reversed.getContent ( ).size ( ) - borderArray.back ( );
 
    automaton::DFA < SymbolType, ext::set < unsigned > > factorAutomaton = automaton::determinize::Determinize::determinize ( automaton::simplify::EpsilonRemoverIncoming::remove ( stringology::indexing::NondeterministicExactFactorAutomaton::construct ( reversed ) ) );
 
    ext::vector < size_t > result;
 
    ext::set < unsigned > state = factorAutomaton.getInitialState ( );
    result.push_back ( 1 );
    for ( const SymbolType & symbol : reversed.getContent ( ) ) {
        state = factorAutomaton.getTransitions ( ).find ( ext::make_pair ( std::move ( state ), symbol ) )->second;
        if ( state.size ( ) >= 2 ) {
            unsigned first = * state.begin ( );
            unsigned second = * std::next ( state.begin ( ) );
 
            result.push_back ( second - first );
        } else {
            result.push_back ( max );
        }
    }
 
    return result;
}
 
} /* namespace properties */
 
} /* namespace string */