AtCoder.String

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

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.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.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.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.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.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.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.0