Understanding Suffix Automaton in depth

Revision en1, by Safrout, 2015-10-06 20:55:54

I am having a lot of trouble with understanding suffix automaton with all it's details.

I have solved about 5 problems that contained very basic applications for it and I am stuck at some points.

I can't really understand how suffix links works, and what the congruence classes are. I know that the best resource is e-maxx site but actually I don't understand Russian and the translators (Google, Yandex , ... etc) sucks. Proofs are translated grammatically wrong and I really can't understand it in depth. The other resources like Crochemore's books are nice but they are actually long and they go beyond what an ACMer needs to understand a data structure.

So, it would be very nice if some one can explain suffix links and congruence classes to me.

Also, there are lots of people do calculate something called the right array in their codes and their comments are either Russian or Chinese and I can't really understand what and why is those 3 loops there.

I hope that someone can really explain all that.

Tags suffix automaton, string suffix structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Safrout 2015-10-06 20:55:54 1061 Initial revision (published)