| 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 sa of s is a permutation of 0,⋯,n−1 such that s[sa[i]..n)<s[sa[i+1]..n) holds for all i=0,1,⋯,n−2.
Constraints
- 0≤n
- 0≤upper≤108
- 0≤x≤upper for all elements x of s.
Complexity
- O(n+upper)-time
Since: 1.0.0.0
suffixArrayBS :: HasCallStack => ByteString -> Vector Int Source #
Calculates suffix array for a ByteString.
Constraints
- 0≤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≤n
Complexity
- O(nlogn)-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[sa[i]..n) and s[sa[i+1]..n).
Constraints
- The second argument is the suffix array of s.
- 1≤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≤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≤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≤n
Complexity
- O(n)
Since: 1.0.0.0