| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.ByteString.SuffixArray
Description
Suffix Array calculation.
Definition
\(\mathcal{sa}[i] = \mathcal{originalOrderOf}(\mathcal{sa}[(n-1-i):])\) where \(\mathcal{originalOrderOf(i)}\) returns the order of i-th suffix.
Synopsis
- saOfNaive :: ByteString -> Vector Int
- saOf :: ByteString -> Vector Int
- sortCyclicShifts :: ByteString -> Vector Int
- sortByCharacter :: ByteString -> (Int, Vector Int, Vector Int)
- sortCyclicShifts' :: Int -> Int -> Int -> Vector Int -> Vector Int -> Vector Int
- lcpOfSa :: ByteString -> Vector Int -> Vector Int
- countUniqueSubstrings :: ByteString -> Int
Documentation
saOfNaive :: ByteString -> Vector Int #
\(O(N^2 \log N)\) Suffix array calculation.
saOf :: ByteString -> Vector Int #
\(O(N \log N)\) Suffix array calculation.
The \(O(N \log N)\) algorithm
Binary lifting with smart sort.
a b a $
ab ba a$ $a
aba$ ba$a a$ab $aba
sortCyclicShifts :: ByteString -> Vector Int #
\(O(N \log N)\) Sorts cyclic substrings of bs of length n.
sortByCharacter :: ByteString -> (Int, Vector Int, Vector Int) #
\(O(N)\) Preprocessing function to sortCyclicShifts.
sortCyclicShifts' :: Int -> Int -> Int -> Vector Int -> Vector Int -> Vector Int #
\(O(N \log N)\) Binary lifting part of sortCyclicShifts.
lcpOfSa :: ByteString -> Vector Int -> Vector Int #
Creates an LCP array of length n-1:
\(\mathcal{lcp}[i'] = \mathcal{lcp}(\mathcal{sa}[i'], \mathcal{sa}[i'+1])\).
countUniqueSubstrings :: ByteString -> Int #
\(O(N \log N)\) Counts unique substrings.