NormalizeRotation.h

Go to the documentation of this file.

 
#pragma once
 
#include <string/CyclicString.h>
 
namespace string {
 
namespace simplify {
 
class NormalizeRotation {
public:
    template < class SymbolType >
    static string::CyclicString < SymbolType > normalize(const string::CyclicString < SymbolType > & string);
};
 
template < class SymbolType >
string::CyclicString < SymbolType > NormalizeRotation::normalize(const string::CyclicString < SymbolType > & string) {
    const ext::vector < SymbolType > & data = string.getContent ( );
    int * f = new int [ 2 * data.size ( ) ]; 
    int k = 0; 
    f [ 0 ] = -1;
    for ( size_t j = 1; j < 2 * data.size ( ); ++j ) {
        int i = f [ j - k - 1 ];
        while ( i != -1 && data [ j % data.size ( ) ] != data [ ( k + i + 1 ) % data.size ( ) ] ) {
            if ( data [ j % data.size ( ) ] < data [ ( k + i + 1 ) % data.size ( ) ] ) k = j - i - 1;
            i = f [ i ];
        }
        if ( i == -1 && data [ j % data.size ( ) ] != data [ k % data.size ( ) ] ) {
            if ( data [ j % data.size ( ) ] < data [ ( k + i + 1 ) % data.size ( ) ] ) k = j;
            f [ j - k ] = -1;
        } else f [ j - k ] = i + 1;
    }
    delete [] f;
 
    if(k == 0)
        return string;
 
    ext::vector < SymbolType > rotated;
    for ( unsigned l = k % data.size ( ); l < data.size() + k % data.size ( ); ++l ) {
        rotated.push_back ( data [ l % data.size ( ) ] );
    }
 
    return string::CyclicString < > { string.getAlphabet ( ), rotated };
}
 
} /* namespace simplify */
 
} /* namespace string */