| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Internal.String
Contents
Description
Internal implementation of AtCoder.String module.
Synopsis
- saNaive :: HasCallStack => Vector Int -> Vector Int
- saDoubling :: HasCallStack => Vector Int -> Vector Int
- saIsImpl :: HasCallStack => Int -> Int -> Vector Int -> Int -> Vector Int
- saIs :: HasCallStack => Vector Int -> Int -> Vector Int
- saIsManual :: HasCallStack => Int -> Int -> Vector Int -> Int -> Vector Int
Suffix array
saNaive :: HasCallStack => Vector Int -> Vector Int Source #
O(n2) Internal implementation of suffix array creation (naive).
Since: 1.0.0.0
saDoubling :: HasCallStack => Vector Int -> Vector Int Source #
O(nlogn) Internal implementation of suffix array creation (doubling).
Since: 1.0.0.0
Arguments
| :: HasCallStack | |
| => Int | naive threshould |
| -> Int | doubling threshould |
| -> Vector Int | string |
| -> Int | upper bounds |
| -> Vector Int | suffix array |
O(n) Internal implementation of suffix array creation (suffix array induced sorting).
Since: 1.0.0.0
O(n) Internal implementation of suffix array creation (suffix array induced sorting).
SA-IS, linear-time suffix array construction. Reference: G. Nong, S. Zhang, and W. H. Chan, Two Efficient Algorithms for Linear Time Suffix Array Construction
Since: 1.0.0.0
Arguments
| :: HasCallStack | |
| => Int | naive threshold |
| -> Int | doubling threshold |
| -> Vector Int | string |
| -> Int | upper bounds |
| -> Vector Int | suffix array |
O(n) Internal implementation of suffix array creation (suffix array induced sorting).
SA-IS, linear-time suffix array construction. Reference: G. Nong, S. Zhang, and W. H. Chan, Two Efficient Algorithms for Linear Time Suffix Array Construction
Since: 1.0.0.0