SuffixArrayNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/SuffixArray.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace indexing {
 
class SuffixArrayNaive {
public:
    template < class SymbolType >
    static indexes::stringology::SuffixArray < SymbolType > construct ( const string::LinearString < SymbolType > & w );
 
};
 
template < class SymbolType >
indexes::stringology::SuffixArray < SymbolType > SuffixArrayNaive::construct ( const string::LinearString < SymbolType > & w ) {
    ext::vector < unsigned > data;
 
    for ( unsigned i = 0; i < w.getContent ( ).size ( ); ++ i )
        data.push_back ( i );
 
    sort ( data.begin ( ), data.end ( ), [ & ] ( unsigned first, unsigned second ) {
            for ( ; first < w.getContent ( ).size ( ) && second < w.getContent ( ).size ( ); ++ first, ++ second ) {
                auto res = w.getContent ( ) [ first ] <=> w.getContent ( ) [ second ];
 
                if ( res != 0 )
                    return res < 0;
            }
 
            // if same up to the maximal size, the shorter suffix is smaller
            return first > second;
    } );
 
    return indexes::stringology::SuffixArray < SymbolType > ( std::move ( data ), string::LinearString < SymbolType > ( w ) );
}
 
} /* namespace indexing */
 
} /* namespace stringology */