LyndonFactoring.h

Go to the documentation of this file.

 
/*
 *
 * Based on code from https://cp-algorithms.com/string/lyndon_factorization.html
 */
 
#pragma once
 
#include <string/LinearString.h>
 
namespace stringology {
 
namespace properties {
 
class LyndonFactoring {
public:
    template < class SymbolType >
    static ext::vector < unsigned > factorize ( const string::LinearString < SymbolType > & string );
 
};
 
template < class SymbolType >
ext::vector < unsigned > LyndonFactoring::factorize ( const string::LinearString < SymbolType > & string ) {
    int n = string.getContent ( ).size ( );
    int i = 0;
    ext::vector < unsigned > factorization;
 
    while ( i < n ) {
        int j = i + 1;
        int k = i;
        while ( j < n && string.getContent ( ) [ k ] <= string.getContent ( ) [ j ] ) {
            if ( string.getContent ( ) [ k ] < string.getContent ( ) [ j ] )
                k = i;
            else
                k ++;
            j ++;
        }
        while ( i <= k ) {
            factorization.push_back ( i );
            i += j - k;
        }
    }
 
    return factorization;
}
 
} /* namespace properties */
 
} /* namespace stringology */