SuffixTrieNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <indexes/stringology/SuffixTrie.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace indexing {
 
class SuffixTrieNaive {
public:
    template < class SymbolType >
    static indexes::stringology::SuffixTrie < SymbolType > construct ( const string::LinearString < SymbolType > & w );
 
};
 
template < class SymbolType >
indexes::stringology::SuffixTrie < SymbolType > SuffixTrieNaive::construct ( const string::LinearString < SymbolType > & w ) {
    ext::trie < SymbolType, std::optional < unsigned > > trie ( std::optional < unsigned > ( w.getContent ( ).size ( ) ) );
 
    for ( unsigned i = w.getContent ( ).size ( ); i > 0; i-- ) {
        unsigned k = i - 1;
        ext::trie < SymbolType, std::optional < unsigned > > * n = & trie;
 
         // inlined slow_find_one from MI-EVY lectures
        while ( n->getChildren ( ).count ( w.getContent ( )[k] ) )
            n = & n->getChildren ( ).find ( w.getContent ( )[k++] )->second;
 
        for ( ; k < w.getContent ( ).size ( ); k++ ) {
            std::optional < unsigned > node = k + 1 < w.getContent ( ).size ( ) ? std::optional < unsigned > ( ) : std::optional < unsigned > ( i - 1 );
            n = & n->getChildren ( ).insert ( std::make_pair ( w.getContent ( )[k], ext::trie < SymbolType, std::optional < unsigned > > ( node ) ) ).first->second;
        }
    }
 
    return indexes::stringology::SuffixTrie < SymbolType > ( w.getAlphabet ( ), std::move ( trie ) );
}
 
} /* namespace indexing */
 
} /* namespace stringology */