PeriodicPrefix.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
#include <string/LinearString.h>
 
namespace string {
 
namespace properties {
 
class PeriodicPrefix {
public:
    template < class SymbolType >
    static ext::pair<ssize_t, ssize_t > construct(const string::LinearString < SymbolType >& string);
};
 
namespace {
    // return period if pattern is periodic, else -1
    template <class SymbolType>
    ssize_t hasShortPeriod ( const ext::vector<SymbolType>& x , size_t prefixLen ) {
        for ( size_t per = 1 ; per <= prefixLen/2 ; ++ per ){
            bool hasPer = true ;
            for ( size_t i = per ; i < prefixLen ; ++ i ) {
                if ( x[i] != x[i - per] ){ hasPer = false ; break ; }
            }
            if ( hasPer ) return per ;
        }
        return -1 ;
    }
}
 
template < class SymbolType >
ext::pair<ssize_t, ssize_t > PeriodicPrefix::construct(const string::LinearString < SymbolType >& string) {
    const auto& x = string.getContent();
 
    ssize_t maxlen = -1 , maxper = -1 ;
    for ( size_t i = 1 ; i <= x.size() ; ++ i ) {
        auto per = hasShortPeriod(x , i) ;
        if ( per != -1 ) {
            maxlen = i ;
            maxper = per ;
        }
    }
 
 
 
    return ext::make_pair( maxlen, maxper) ;
}
 
 
} /* namespace properties */
 
} /* namespace string */