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

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

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.

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

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

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

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

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