Data.SuffixArray

Suffix array library main module

Documentation

data SuffixArray a

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)

Methods

(==) :: SuffixArray a -> SuffixArray a -> Bool

(/=) :: SuffixArray a -> SuffixArray a -> Bool

Ord a => Ord (SuffixArray a)

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)

Methods

showsPrec :: Int -> SuffixArray a -> ShowS

show :: SuffixArray a -> String

showList :: [SuffixArray a] -> ShowS

suffixArray :: Ord a => [[a]] -> SuffixArray a

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)

suffixArrayOne :: Ord a => [a] -> SuffixArray a

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)

data Alpha a

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)

Methods

(==) :: Alpha a -> Alpha a -> Bool

(/=) :: Alpha a -> Alpha a -> Bool

Ord a => Ord (Alpha a)

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)

Methods

showsPrec :: Int -> Alpha a -> ShowS

show :: Alpha a -> String

showList :: [Alpha a] -> ShowS

justAlphas :: SuffixArray a -> [Alpha a]

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

justLcp :: SuffixArray a -> [Int]

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

justSuffixes :: SuffixArray a -> [Int]

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