Data.SuffixArray

Description

Suffix array library main module

Synopsis

Documentation

Holds the computed suffix array data

Constructors

SuffixArray
Fields toSuffixes :: UArray Int Int The actual array of suffixes in lexicographic order. toAlphas :: Array Int (Alpha a) The original string(s) with `Sentinal` values included after each string. toLcp :: UArray Int Int Longest Common Prefix of each suffix with the previous one in lexicographic order

Instances

Eq a => Eq (SuffixArray a) Source #
Methods (==) :: SuffixArray a -> SuffixArray a -> Bool # (/=) :: SuffixArray a -> SuffixArray a -> Bool #
Ord a => Ord (SuffixArray a) Source #
Methods compare :: SuffixArray a -> SuffixArray a -> Ordering # (<) :: SuffixArray a -> SuffixArray a -> Bool # (<=) :: SuffixArray a -> SuffixArray a -> Bool # (>) :: SuffixArray a -> SuffixArray a -> Bool # (>=) :: SuffixArray a -> SuffixArray a -> Bool # max :: SuffixArray a -> SuffixArray a -> SuffixArray a # min :: SuffixArray a -> SuffixArray a -> SuffixArray a #
Show a => Show (SuffixArray a) Source #
Methods showsPrec :: Int -> SuffixArray a -> ShowS # show :: SuffixArray a -> String # showList :: [SuffixArray a] -> ShowS #

Compute the suffix array of the given string(s) concatenated together with Sentinals after each.

worst case O(n lg n) time (where n is the sum of the string lengths + the number of strings)

Convenience function to compute the suffix array of a single string. (Still gets a Sentinal at the end)

worst case O(n lg n) time (where n is the length of the string)

A character in a string (or set of strings) we're going to compute the suffix array of. Includes Sentinal markers for the end of strings.

Constructors

Sentinal Int	Used to mark the end of a string. The `Int` parameter is used to encode which string this is the end of, in cases where there are multiple.
Alpha a	An actual character in the string.

Instances

Eq a => Eq (Alpha a) Source #
Methods (==) :: Alpha a -> Alpha a -> Bool # (/=) :: Alpha a -> Alpha a -> Bool #
Ord a => Ord (Alpha a) Source #
Methods compare :: Alpha a -> Alpha a -> Ordering # (<) :: Alpha a -> Alpha a -> Bool # (<=) :: Alpha a -> Alpha a -> Bool # (>) :: Alpha a -> Alpha a -> Bool # (>=) :: Alpha a -> Alpha a -> Bool # max :: Alpha a -> Alpha a -> Alpha a # min :: Alpha a -> Alpha a -> Alpha a #
Show a => Show (Alpha a) Source #
Methods showsPrec :: Int -> Alpha a -> ShowS # show :: Alpha a -> String # showList :: [Alpha a] -> ShowS #

Convenience function to just give a list characters in the concatenated original strings.

Convenience function to just give a list of the longest common prefix of every suffix with the previous suffix in lexicographic order.

Convenience function to just give a list of the suffixes in lexicographic order.