terserah's blog

Terminating character in suffix array
By terserah, history, 9 years ago, In English

Hi!

I just learned to implement suffix array. I got quite confused about why i need to add a terminating character to my input string such as a '$' or '#'. I tried solving problem without the terminating character, some got accepted, some got WA. Any comments? Thank you so much!

FYI, i learned suffix array from CP 3 by Steven and Felix Halim.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It depends on implementation, but string like 'aaaaa' can lead comparison over the string.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your algorithm may be sorting not suffixes but cycle-shifts so adding some character which has less value than the others solves the problem :)

→ Reply