Repetition.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
#include <string/LinearString.h>
 
namespace string {
 
namespace properties {
 
class Repetition {
public:
    template < class SymbolType >
    static ext::tuple<size_t, size_t, size_t> construct(const string::LinearString < SymbolType >& string);
};
 
template < class SymbolType >
ext::tuple<size_t, size_t, size_t> Repetition::construct(const string::LinearString < SymbolType >& string) {
    const auto& x = string.getContent();
    size_t maxlen = 0 , first = 0 , second = 0 ;
    for ( size_t i = 0 ; i < x.size() ; ++ i ) {
        for ( size_t j = i + 1 ; j < x.size() ; ++ j ) {
            size_t k = 0 ;
            while ( i + k < j && j + k < x.size() && x[i + k] == x[j + k]) ++ k ;
            if ( k > maxlen ) {
                maxlen = k ;
                first = i ;
                second = j ;
            }
        }
    }
    return ext::make_tuple(maxlen, first, second) ;
}
 
} /* namespace properties */
 
} /* namespace string */