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 .