fullaccepted's blog

Dynamic programming on suffix automata/suffix trees
By fullaccepted, 13 years ago, In English

Hello everyone!
Recently, I studied Suffix Automata from e-maxx's site. I think, I got it.
After solving some problems from SIS(LKSH) archives I moved to Online Judges. Didn't find any related problems on timus, found some on CodeForces. They were successfully done.

Problem I go stuck with is Names for Babies, please help to solve it!

Actually, I got some problems with constructing dynamic on suffix tree for linear time. Can you give some hints for solving such type of problems? Any main ideas or anything... I understood dynamic on suffix structures of another type(example is problem Censored on timus), but types like "number of different substrings", "total length of different substrings", etc. look like something difficult.

Any help is welcomed!

[picture of bicycle here]

languages I understand: english, русский, turkce, 中國, 한국의, Deutsch...
Just jocking, at least I understand first two of them.


  • Vote: I like it
  • +11
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I have ac the names for babies problem with n(lgn)^2 suffix array then n*(LCP of complexity lgn)=nlgn . Think like this, if 2 suffix has lcp of size l, then for distinct subset of lengths less then l, you have to considered only one of the suffix. Also for any suffix, the string which have longest LCP with it, is one of the adjacent one with it in suffix array.
→ Reply