Why in the suffix array is it necessary to put a character like '$' in the end?
I do not understand why it does not work if that character is missing!
Thanks in advance!
№ | Пользователь | Рейтинг |
---|---|---|
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 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Why in the suffix array is it necessary to put a character like '$' in the end?
I do not understand why it does not work if that character is missing!
Thanks in advance!
Название |
---|
It's not necessary to add it for suffix array, it's useful when building a suffix tree to make sure that no suffix is a prefix of another
The algorithm I'm aware about sorts cyclic shifts of the string, not suffixes. In that case, lack of
$
in the end would result in random ordering of suffixes which are prefixes of each other (i.e. corresponding cyclic shifts are strictly equal). E.g. for stringabab
suffixesab
andabab
would be ordered pretty much randomly, while the former should come first.The reason above is not always true: e.g. one may use a stable sorting algorithm and arrange suffixes more carefully in the beginning.