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.
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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 8 | maroonrk | 133 |
| 10 | qwexd | 130 |
It can be solved using suffix array. If you don't know what it is there a course in the edu section.
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?
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.
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?
Ohh sorry I was wrong. I didn't understand the text.