mcsp-algorithms-0.1.0: Algorithms for Minimum Common String Partition (MCSP) in Haskell.
Safe HaskellSafe-Inferred
LanguageGHC2021

MCSP.Data.RadixTree.Suffix

Description

A compressed trie of string suffixes.

Synopsis

Documentation

type SuffixTree a = RadixTreeMap a (Suffix a) Source #

A set of suffixes for a pair of strings.

Represented by a suffix tree.

construct :: Ord a => String a -> String a -> SuffixTree a Source #

O(?) Constructs suffix tree for a pair of strings.

>>> construct "aba" "ba"
Tree (Suffix Both ) [a :~> Tree (Suffix Both a) [ba :~> Tree (Suffix First aba) []],ba :~> Tree (Suffix Both ba) []]

findMax :: Ord a => SuffixTree a -> Maybe (String a) Source #

O(n log r) Retrieves the maximum common prefix of all suffixes.

>>> findMax (construct "abab" "baba")
Just bab