a tip on longest common substring problem using suffix array

Revision en1, by MOOONI, 2020-07-01 10:12:49

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English MOOONI 2020-07-01 10:12:49 851 Initial revision (published)