| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.String
Contents
Description
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.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 Source #
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 \(\mathrm{sa}\) of \(s\) is a permutation of \(0, \cdots, n-1\) such that \(s[\mathrm{sa}[i]..n) < s[\mathrm{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
- \(O(n + \mathrm{upper})\)-time
Since: 1.0.0.0
suffixArrayBS :: HasCallStack => ByteString -> Vector Int Source #
Calculates suffix array for a ByteString.
Constraints
- \(0 \leq n\)
Complexity
- \(O(n)\)-time
Since: 1.0.0.0
suffixArrayOrd :: (HasCallStack, Ord a, Unbox a) => Vector a -> Vector Int Source #
Calculates suffix array for a Ord type vector.
Constraints
- \(0 \leq n\)
Complexity
- \(O(n \log n)\)-time
- \(O(n)\)-space
Since: 1.0.0.0
LCP array
Arguments
| :: (HasCallStack, Ord a, Unbox a) | |
| => Vector a | A vector representing a string |
| -> Vector Int | Suffix array |
| -> Vector Int | LCP array |
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[\mathrm{sa}[i]..n)\) and \(s[\mathrm{sa}[i+1]..n)\).
Constraints
- The second argument is the suffix array of \(s\).
- \(1 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0.0
Arguments
| :: HasCallStack | |
| => ByteString | String |
| -> Vector Int | Suffix array |
| -> Vector Int | LCP array |
ByteString variant of lcpArray.
Constraints
- The second argument is the suffix array of \(s\).
- \(1 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0.0
Z algorithm
zAlgorithm :: (Ord a, Unbox a) => Vector a -> Vector Int Source #
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.0
zAlgorithmBS :: ByteString -> Vector Int Source #
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.0