NyldonFactoring.h

Go to the documentation of this file.

 
/*
 *
 * Based on code from arXiv:1804.09735
 */
 
#pragma once
 
#include <string/LinearString.h>
 
#include <alib/deque>
 
namespace stringology {
 
namespace properties {
 
class NyldonFactoring {
public:
    template < class SymbolType >
    static ext::vector < unsigned > factorize ( const string::LinearString < SymbolType > & string );
 
};
 
template < class SymbolType >
ext::vector < unsigned > NyldonFactoring::factorize ( const string::LinearString < SymbolType > & string ) {
    unsigned n = string.getContent ( ).size ( );
    ext::deque < ext::vector < SymbolType > > NyIF { ext::vector < SymbolType > { string.getContent ( ) [ n - 1 ] } };
    for ( unsigned i = 2; i <= n; ++ i ) {
        NyIF.push_front ( ext::vector < SymbolType > { string.getContent ( ) [ n - i ] } );
        while ( NyIF.size ( ) >= 2 && NyIF [ 0 ] > NyIF [ 1 ] ) {
            ext::vector < SymbolType > tmp = std::move ( NyIF [ 0 ] );
            tmp.insert ( tmp.end ( ), NyIF [ 1 ].begin ( ), NyIF [ 1 ].end ( ) );
 
            NyIF.pop_front ( );
            NyIF.pop_front ( );
            NyIF.push_front ( std::move ( tmp ) );
        }
    }
 
    ext::vector < unsigned > factorization;
    unsigned i = 0;
    for ( const ext::vector < SymbolType > & factor : NyIF ) {
        factorization.push_back ( i );
        i += factor.size ( );
    }
    return factorization;
}
 
} /* namespace properties */
 
} /* namespace stringology */