MaximalSuffix.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
#include <string/LinearString.h>
 
namespace string {
 
namespace properties {
 
class MaximalSuffix {
public:
    template < class SymbolType >
    static ext::pair<size_t, size_t > construct(const string::LinearString < SymbolType >& string);
 
    template < class SymbolType >
    static ext::pair<size_t, size_t > constructReversed(const string::LinearString < SymbolType >& string);
};
 
template < class SymbolType >
ext::pair<size_t, size_t > MaximalSuffix::construct(const string::LinearString < SymbolType >& string) {
    const auto& x = string.getContent();
    size_t i = 0, j = 1, k = 1, p = 1;
 
    while (j + k <= x.size()) {
        auto A = x[i + k - 1];
        auto a = x[j + k - 1];
        if ( a < A ) { j = j + k ; k = 1 ; p = j - i ; }
        else if ( a == A ) {
            if ( k == p ) { j = j + p ; k = 1 ; } else { k = k + 1 ;}
        } else { i = j ; j = i + 1 ; k = 1 ; p = 1 ;}
    }
    return ext::make_pair( i , p );
}
 
template < class SymbolType >
ext::pair<size_t, size_t > MaximalSuffix::constructReversed(const string::LinearString < SymbolType >& string) {
    const auto& x = string.getContent();
    size_t i = 0, j = 1, k = 1, p = 1;
 
    while (j + k <= x.size()) {
        auto A = x[i + k - 1];
        auto a = x[j + k - 1];
        if ( a > A ) { j = j + k ; k = 1 ; p = j - i ; }
        else if ( a == A ) {
            if ( k == p ) { j = j + p ; k = 1 ; } else { k = k + 1 ;}
        } else { i = j ; j = i + 1 ; k = 1 ; p = 1 ;}
    }
    return ext::make_pair( i , p );
}
 
} /* namespace properties */
 
} /* namespace string */