suffixarray- n log n implementation of suffix array.

MaintainerDaniël de Kok <> Victor Denisov <>
Safe HaskellSafe-Infered



Construction of suffix arrays (arrays ordered by suffix). Given an array d elements, the suffix array is a sorted array of the sub-arrays in d. For instance, the suffix array of banana apple pear apple is:

  • apple
  • apple pear apple
  • banana apple pear apple
  • pear apple



data SuffixArray a Source


SuffixArray (Vector a) (Vector Int) 


Show a => Show (SuffixArray a) 

suffixArray :: (Ix a, Ord a, Bounded a) => Vector a -> SuffixArray aSource

Generate a suffix array as list.

simpleEquator :: (Ix a, Ord a, Bounded a) => Vector a -> Vector Int -> EquatorSource

fancyEquator :: (Ix a, Ord a, Bounded a) => Vector a -> Vector Int -> Int -> Int -> EquatorSource

composeLists :: Vector Int -> Vector Int -> Vector IntSource

  • Build composition of two lists. First argument is source list. - Second argument is vector of indexes. Elements of first list should - be reordered accordingly to indexes in the second argument.

fromList :: (Ix a, Ord a, Bounded a) => [a] -> SuffixArray aSource

fromList constructs a suffix array from a list of elements.

toList :: SuffixArray a -> [[a]]Source

toList constructs a list from a suffix array.

elems :: SuffixArray a -> Vector (Vector a)Source

elems provides a vector of each element in the suffix array. One element of the suffix array contains the full data array.