Safe Haskell | None |
---|---|
Language | GHC2021 |
It contains string algorithms.
Let s
be a string. We denote the substring of s
between \(a\)-th and \(b - 1\)-th character
by s[a..b)
.
Examples
Suffix Array and LCP Array
>>>
import AtCoder.String qualified as S
>>>
import Data.ByteString.Char8 qualified as BS
>>>
let s = BS.pack "aab"
>>>
let sa = S.suffixArrayBS s
>>>
S.lcpArrayBS s sa
[1,0]
Z Algorithm
>>>
import AtCoder.String qualified as S
>>>
import Data.ByteString.Char8 qualified as BS
>>>
let s = BS.pack "abab"
>>>
S.zAlgorithmBS s
[4,0,2,0]
Since: 1.0.0
Synopsis
- suffixArray :: HasCallStack => Vector Int -> Int -> Vector Int
- suffixArrayBS :: HasCallStack => ByteString -> Vector Int
- suffixArrayOrd :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int
- lcpArray :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int -> Vector Int
- lcpArrayBS :: HasCallStack => ByteString -> Vector Int -> Vector Int
- zAlgorithm :: (Ord a, Unbox a) => Vector a -> Vector Int
- zAlgorithmBS :: ByteString -> Vector Int
Suffix array
suffixArray :: HasCallStack => Vector Int -> Int -> Vector Int #
Calculates suffix array for a Int
vector.
Given a string s
of length \(n\), it returns the suffix array of s
. Here, the suffix array
sa
of s
is a permutation of \(0, \cdots, n-1\) such that s[sa[i]..n) < s[sa[i+1]..n)
holds
for all \(i = 0,1, \cdots ,n-2\).
Constraints
- \(0 \leq n\)
- \(0 \leq \mathrm{upper} \leq 10^8\)
- \(0 \leq x \leq \mathrm{upper}\) for all elements \(x\) of \(s\).
Complexity
- (3) \(O(n + \mathrm{upper})\)-time
Since: 1.0.0
suffixArrayBS :: HasCallStack => ByteString -> Vector Int #
Calculates suffix array for a ByteString
.
Constraints
- \(0 \leq n\)
Complexity
- (1) \(O(n)\)-time
Since: 1.0.0
suffixArrayOrd :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int #
Calculates suffix array for a Ord
type vector.
Constraints
- \(0 \leq n\)
Complexity
- (2) \(O(n \log n)\)-time, \(O(n)\)-space
Since: 1.0.0
LCP array
lcpArray :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int -> Vector Int #
Given a string s
of length \(n\), it returns the LCP array of s
. Here, the LCP array of
s
is the array of length \(n-1\), such that the \(i\)-th element is the length of the LCP
(Longest Common Prefix) of s[sa[i]..n)
and s[sa[i+1]..n)
Constraints
- The second argument is the suffix array of
s
. - \(1 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0
lcpArrayBS :: HasCallStack => ByteString -> Vector Int -> Vector Int #
ByteString
verison of lcpArray
.
Constraints
- The second argument is the suffix array of
s
. - \(1 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0
zAlgorithm :: (Ord a, Unbox a) => Vector a -> Vector Int #
Given a Ord
vector of length \(n\), it returns the array of length \(n\), such that the
\(i\)-th element is the length of the LCP (Longest Common Prefix) of s[0..n)
and s[i..n)
.
Constraints
- \(n \leq n\) ==== Complexity
- \(O(n)\)
Since: 1.0.0
Z algorithm
zAlgorithmBS :: ByteString -> Vector Int #
Given a string of length \(n\), it returns the array of length \(n\), such that the \(i\)-th
element is the length of the LCP (Longest Common Prefix) of s[0..n)
and s[i..n)
.
Constraints
- \(n \leq n\) ==== Complexity
- \(O(n)\)
Since: 1.0.0