yashi's blog

The Special Character At The End Of The String — Suffix Array
By yashi, history, 9 years ago, In English

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 .

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

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply