upobir's blog

By upobir, history, 7 weeks ago,

I was happily browsing internet 2 days ago until I saw this problem String Transform. Been stuck at it for two days now, and the best I could come up with is a rough $O(n^2)$ idea. Would be greatful for some hints.

• +7

 » 7 weeks ago, # | ← Rev. 2 →   -6 It can be solved using suffix array. If you don't know what it is there a course in the edu section.
•  » » 7 weeks ago, # ^ |   0 I know suffix array, but the application here isn't obvious to me. I have all rotation's last character, which is a permutation of the original string, so computing this string's suffix arrays shouldn't be useful, right? So what do I build the suffix array of?
•  » » » 7 weeks ago, # ^ |   0 You can just build the suffix array of the original string. Then replace every character of the original string with the one before (so this is the last character of the string starting at this position), and sort this new string based on the suffix array.
•  » » » » 7 weeks ago, # ^ |   0 But I do not have the original string? For example in the sample I am given "cb#ab" the final string, I have to restore the original string myself. Or by original string are you referring to the input string?
•  » » » » » 7 weeks ago, # ^ |   0 Ohh sorry I was wrong. I didn't understand the text.