### yashi's blog

By yashi, history, 4 years ago, ,

Hey codeforces,

I wanna ask about the special character that be appended to the string when building its suffix array, Why this character is important ?
I do understand the functionality of it in the suffix tree and in the construction of the suffix array using DC3 (Difference Cover) algorithm (actually 2 special characters should be appended in this algo) .
But when neither the construction nor the traversal requires it why to append it !?

This question came out after solving this problem (11512 — GATTACA) (given a string find the LRS (Longest Repeated Substring) and how many times the LCS occurs) , when I was solving it I faced such an odd issue I was almost sure that everything is right but still getting WA more than 10 times, I tried more than 100 testcases and my code could produce the right output for them .
Eventually just added this line to my code strcat(text,"\$"); and got AC, I spent my whole day trying to figure out what a spell this line does, but ended up with nothing .
Here's my code, you can try it yourself .
Any explanation, elaboration, and help in this issue would be appreciated,

Thank you all :D .

• +1

 » 4 years ago, # |   +1 This is just a guess but your code might work without terminating character if you started counting rank from 1 (int r=1; tmpRank[sufArr[0]] = 1). In current implementation rank 0 seems to conflict with i+k < n ? rank[i+k] : 0.
•  » » 4 years ago, # ^ |   0 Yeeeah, it is :D . Thank you very much for pointing that out :D got AC without a terminating character . Thanks again it really drove me mad, now I can move on .