| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi All,
Can someone share their ideas on how to do the following problem in O(n): http://www.geeksforgeeks.org/lexicographically-smallest-rotated-sequence-set-2/
I have found on wikipedia that it can be done in O(n). I am not able to understand the booth's algorithm given on wikipedia.
Can someone share their approach to solve this problem in O(n).
Thanks in advance
What if you concatenate the input sequence with itself, then compute the suffix tree of that. The answer should be the least suffix that starts in the original sequence.
Not entirely sure that's true, I could have missed a corner case or it could just be totally broken. But it sounds plausible to me.
You can of course use suffix arrays instead, though the linear-time suffix array constructions I've seen are fairly advanced.
Old TopCoder thread with discussion on this problem
Double your string s. Now you have string a, that contains every cyclic shift of s as substring. Now build suffix automata on a. Now just start in root vertex and go |s| times chosing edge with minimal letter on it. It actually O(nlog|alph|), where |alph| is alphabet size, but log 26 is small, so it's O(n)