The Special Character At The End Of The String — Suffix Array

Revision en1, by yashi, 2015-12-15 00:15:24

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 .

Tags suffix-array, special-character

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yashi 2015-12-15 00:15:24 1432 Initial revision (published)