0
$\begingroup$

I found an implementation of suffix arrays here (not sure if it's the most efficient so if there's any better I'd be glad to know).

For a given string:

data = '1034408'*10

It generates the following suffix array:

suffix_array = [64, 57, 50, 43, 36, 29, 22, 15, 8, 1, 68, 61, 54, 47, 40, 33, 26, 19, 12, 5, 63, 56, 49, 42, 35, 28, 21, 14, 7, 0, 65, 58, 51, 44, 37, 30, 23, 16, 9, 2, 67, 60, 53, 46, 39, 32, 25, 18, 11, 4, 66, 59, 52, 45, 38, 31, 24, 17, 10, 3, 69, 62, 55, 48, 41, 34, 27, 20, 13, 6]

Having:

len(suffix_array) = 70
max(suffix_array) = 69
suffix_array.index(max(suffix_array)) = 60

Is a suffix tree better suited for this task?

Improve this question
$\endgroup$
4
  • $\begingroup$ As you can see in the Wikipedia page: en.wikipedia.org/wiki/Longest_repeated_substring_problem a suffix tree can be used for this task (to solve it optimally). I don't really know a lot about suffix arrays, but from what I understand, if you can use it to solve the question in $O(n)$ time, it doesn't really matter. $\endgroup$ Commented Jun 13, 2021 at 23:14
  • $\begingroup$ "Better" by what criteria? I don't see the task described in the body of the post. $\endgroup$ Commented Jun 14, 2021 at 4:33
  • $\begingroup$ @D.W. more efficient (both temporal and spatial). $\endgroup$ Commented Jun 14, 2021 at 11:04
  • $\begingroup$ This might be hard to answer in a useful way. They have the same asymptotic efficiency. Constant factors are hard to analyze as they depend on the architecture. It's not clear to me which of those you are asking about. $\endgroup$ Commented Jun 14, 2021 at 20:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.