Please read the new rule regarding the restriction on the use of AI tools. ×

skloj's blog

Criteria to decide when a Suffix Tree is required (instead of a suffix array)
By skloj, history, 3 years ago, In English

I was curious to know if anyone uses Suffix trees instead of Suffix arrays. I just settled down using Suffix arrays because I was not able to implement a fast Suffix tree, but not sure if people here had a different experience. For instance, is there a problem that can be solved only with a Suffix trees but not with Suffix arrays?

Thank you,

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A suffix array plus the LCP array can do anything that a suffix tree can do. Additionally, suffix arrays are usually faster and use less memory, so it's unlikely that there are any problems that can only be solved with suffix trees.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Great answer, thanks for that. You are right, probably sticking just to using suffix arrays is enough. I guess the only advantage of suffix trees is they are easier to understand if you have worked already with Automatas. Also, it is useful for solving problems requiring online-construction, but I guess that requirement never really comes up in competitive programming.

    → Reply