public class SuffixArrays
extends java.lang.Object
Modifier and Type | Class and Description |
---|---|
static interface |
SuffixArrays.LongArray
An array whose values and indices are primitive longs.
|
Modifier and Type | Method and Description |
---|---|
static void |
buildSuffixArray(SuffixArrays.LongArray s,
SuffixArrays.LongArray sa,
SuffixArrays.LongArray fc,
SuffixArrays.LongArray sc,
long n)
Builds a suffix array for the given string in O(n*log^2(n)) time.
|
static long[] |
search(SuffixArrays.LongArray s,
SuffixArrays.LongArray sa,
SuffixArrays.LongArray p,
long n,
long m)
Searches the given pattern in the given string in O(m*log(n)) time.
|
public static void buildSuffixArray(SuffixArrays.LongArray s, SuffixArrays.LongArray sa, SuffixArrays.LongArray fc, SuffixArrays.LongArray sc, long n)
s
- the string for which to build the suffix array.sa
- the long array in which to build the suffix array.fc
- an auxiliary array.sc
- an auxiliary array.n
- the length of the string and both auxiliary arrays.public static long[] search(SuffixArrays.LongArray s, SuffixArrays.LongArray sa, SuffixArrays.LongArray p, long n, long m)
s
- the string.sa
- the suffix array of the string.p
- the pattern (substring) to search.n
- the length of the string.m
- the length of the pattern.long
array of length 2, either {-1, -1} in case the
pattern is not found in the string, or whose values indicate the starting
(inclusive) and ending (exclusive) indices of the matched pattern in the
suffix array. In other words, a result like {a, b} would indicate that
for every value i in [a,b), sa[i] is an index of an occurrence of pattern
p in string s.