MOOONI's blog

a tip on longest common substring problem using suffix array
By MOOONI, history, 4 years ago, In English

Hello codeforces. I was solving this problem in EDU part that I faced a bug. as said in the video, to find the longest common substring of two strings s and t we should first build the suffix array of s + # + t. I did this and this caused me RE on test 2. and it turned out that the reason was the character # is smaller than the character (dollar) that we add to the end of the string at the beginning of building suffix array. but it was said that character (dollar) has to be the smallest character among all characters of the string. so to fix this issue we can use character ~ instead of #. and ~ is also bigger than character z. so we won't face any problem then. I wanted to make you aware of this.

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I think we can use char('z'+ 1) when 'z' is biggest character, instead of '#' or '$', to prevent bugs like this.

→ Reply