Suffix array DC3 algorithm

Question

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 found here.

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:

for (int i = 0; i < 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
 }

Please help me understand this portion. (This code is from page 20 of the pdf)

The part that I do understand is that name is the variable which is different for different triplets and same for exactly same triplets. But I don't understand how the index of R is used here? — Fluvid
– Fluvid, Commented Sep 3, 2013 at 18:45

Vikas Awadhiya · Accepted Answer · 2022-08-27 17:12:38Z

3

Repository DC3 Algorithm contains tutorial document and implementation is available in C++.

edited Aug 27, 2022 at 17:12

answered Feb 15, 2021 at 14:24

Vikas Awadhiya

3081 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

shss0123 · Accepted Answer · 2013-12-23 09:28:14Z

0

After radix sort, adjacent element in SA12[] may equal, so there is a if in the loop, as for R1 and R2, give an example:

original array is [y a b b a d a b b a d o], n = 12, index range is [0,11] R1 = [1,4,7,10] R2=[2,5,8,11], "if (SA12[i] % 3 == 1) " indicates SA12[i] belong to R1, else belong to R2, R is concentration of R1 and R2.

hope this helps.

answered Dec 23, 2013 at 9:28

shss0123

12 bronze badges

Collectives™ on Stack Overflow

Suffix array DC3 algorithm

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related