| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
I was curious to know if anyone uses Suffix trees instead of Suffix arrays. I just settled down using Suffix arrays because I was not able to implement a fast Suffix tree, but not sure if people here had a different experience. For instance, is there a problem that can be solved only with a Suffix trees but not with Suffix arrays?
Thank you,
A suffix array plus the LCP array can do anything that a suffix tree can do. Additionally, suffix arrays are usually faster and use less memory, so it's unlikely that there are any problems that can only be solved with suffix trees.
Great answer, thanks for that. You are right, probably sticking just to using suffix arrays is enough. I guess the only advantage of suffix trees is they are easier to understand if you have worked already with Automatas. Also, it is useful for solving problems requiring online-construction, but I guess that requirement never really comes up in competitive programming.
Do you know there's also suffix automaton?