patl

STL-compatible, high-performance template containers and auxiliary classes useful for stringology

> Trie containers - trie_set & trie_map.
> Online suffix tree containers - suffix_set & suffix_map - O(N) both time & space, 16 bytes per symbol, alphabet-independent.
> Iterators over each type of containers - standard (const_)(reverse_)iterator, special (post|pre|level)order_iterator for respective tree traversals.
> Partial match iterators (const_)partimator (joker pattern filter, Hamming & Levenshtein automata filter).
> suffix_cont-special match_iterator & (super_)maxrep_iterator for matching statistics and (super)maximal repeats.
> Lowest common ancestor (LCA) O(1) time requests after O(N) postprocessing of the suffix_cont - lca_oracle.
> Small & clever demo programs.

Tags

  suffix distance lca lz77 hamming tree stl lowest sort patricia external ancestor bwt cpp maximal trie common repeats sorting levenshtein template

Share