2
$\begingroup$

There is a lot in the literature about linear time constructions for suffix arrays; DC3, radixSA46, and more...

However, these, I believe, are only for suffix arrays; with a single string input. Are there fast algorithms for generalised suffix arrays, which have multiple string inputs?

for example

strings = ["maps$", "maps$, "mops$"]

GSA = createGenSuf(strings)

for (suffix in GSA) {
    print suffix;
    print strings[suffix]
}

where the output would be:

(0,4)
$

(1,4)
$

(2,4)
$

(0,1)
aps$

(1,1)
aps$

(0,0)
maps$

(1,0)
maps$

(2,0)
mops$

(2,1)
ops$

(0,2)
ps$

(1,2)
ps$

(2,2)
ps$

(0,3)
s$

(1,3)
s$

(2,3)
s$

I'm currently using the naive O(n^2 * log n) merge sort. Where n is the number of characters. There must be something faster available but i'm having a hard time identifying it in literature.

Regards to all who read, and anyone who offers a better algorithm

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.