Блог пользователя AmericanPsycho

Автор AmericanPsycho, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 string abab suffixes ab and abab 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.