SuffixArray
Defined in: packages/data/src/substring/suffix-array.ts:16
A substring index over one string: every suffix, sorted.
Answers “where does this substring occur” in O(m log n) for a needle of
length m, against the O(n·m) a scan would cost — so it pays for itself as
soon as one text is searched more than a few times. Construction is O(n log²
n) and the index is static: to search different text, build another.
The array holds the starting offset of each suffix in sorted order, so every occurrence of a needle is a contiguous run, found by two binary searches.
Space complexity: O(n) machine words beside the text itself.
Implements
Section titled “Implements”ISubstringIndex<string>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new SuffixArray(
text):SuffixArray
Defined in: packages/data/src/substring/suffix-array.ts:19
Parameters
Section titled “Parameters”string
Returns
Section titled “Returns”SuffixArray
Properties
Section titled “Properties”
readonlytext:string
Defined in: packages/data/src/substring/suffix-array.ts:19
Methods
Section titled “Methods”count()
Section titled “count()”count():
number
Defined in: packages/data/src/substring/suffix-array.ts:24
The number of suffixes, i.e. the text’s length.
Returns
Section titled “Returns”number
countOf()
Section titled “countOf()”countOf(
needle):number
Defined in: packages/data/src/substring/suffix-array.ts:72
How many times needle occurs. O(m log n), without materialising them.
Parameters
Section titled “Parameters”needle
Section titled “needle”string
Returns
Section titled “Returns”number
has(
needle):boolean
Defined in: packages/data/src/substring/suffix-array.ts:63
O(m log n).
Parameters
Section titled “Parameters”needle
Section titled “needle”string
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”order()
Section titled “order()”order(): readonly
number[]
Defined in: packages/data/src/substring/suffix-array.ts:29
The starting offsets of every suffix, in sorted order.
Returns
Section titled “Returns”readonly number[]
search()
Section titled “search()”search(
needle):IterableIterator<number>
Defined in: packages/data/src/substring/suffix-array.ts:40
Every starting offset where needle occurs, in ascending order. O(m log n)
to locate, plus O(k log k) to sort the k occurrences.
An empty needle matches at every offset, String.prototype.indexOf’s
convention.
Parameters
Section titled “Parameters”needle
Section titled “needle”string
Returns
Section titled “Returns”IterableIterator<number>