title: Suffix array DC3 algorithm
body: <p>I am going over the DC3 algorithm, the linear time algorithm for construction of suffix arrays. I am unable to understand a technique in the paper which can be <a href="http://algo2.iti.kit.edu/documents/jacm05-revised.pdf" rel="nofollow">found here</a>.</p>
  
  <p>I am unable to understand how the renaming, mentioned on page 6 of the paper, is done. How is the renaming done as per Step 1. The relevant section of code from appendix is:</p>
  
  <pre><code>for (int i = 0; i &lt; n02; i++) 
  {
       if (T[SA12[i]] != c0 || T[SA12[i]+1] != c1 || T[SA12[i]+2] != c2)
       { 
            name++; c0 = T[SA12[i]]; c1 = T[SA12[i]+1]; c2 = T[SA12[i]+2]; 
       }
       if (SA12[i] % 3 == 1) 
       { 
            R[SA12[i]/3] = name; 
       } // write to R1
       else
       { 
            R[SA12[i]/3 + n0] = name; 
       } // write to R2
   }
  </code></pre>
  
  <p>Please help me understand this portion. (This code is from page 20 of the pdf)</p>