AmericanPsycho's blog

Suffix array
By AmericanPsycho, history, 7 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply