Suffix automaton on large alphabet

Revision en1, by radoslav11, 2018-10-29 12:22:05

Hello!

During yesterdays round I solved (or tried solving) problem D with suffix automaton — it's very simple after copying SA's code (link to code). But unfortunately it TLE like the majority of solutions. So I just thought "Eh, I guess solutions aren't supposed to pass". But today I actually realized that I'm not sure if my solution is actually — in the part where we create the "clone" node, we copy the adjacent nodes of the given node to the adjacency list of the clone. This might actually result in O(Σ) complexity and if this happens many times the solution will obviously be slow. But I cannot find a sample, where we happen to copy large adjacency lists many times. Can you help me with that?

So generally my question is:

If we use suffix automaton on large alphabet what is there worst time complexity?

PS: We can achieve if we use persistent trees to keep the adjacency lists, but I find this to be a very ugly approach.

Tags string suffix structures, suffix automata, suffix automaton

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English radoslav11 2018-10-29 12:27:25 2 Tiny change: 'hat is there worst ti' -> 'hat is the worst ti'
en1 English radoslav11 2018-10-29 12:22:05 1210 Initial revision (published)