When applying the DC3/Skew algorithm to the string yabadabado, I can't quite get it to sort correctly. This issue happens in other cases, but this is a short example to show it.

This first table is for reference: enter image description here

These are the triples of R12

enter image description here

We have a tie between i = 1, and i = 5 since both their triples are aba.

We now need to get the suffix array of the ranks R' through recursing, but we can quickly break this tie since i_1 = [1,3] > i_5 = [1,2] which implies that the suffix starting at i = 5 should come before i = 1. Recursing returns the same result with R'5 < R'1.

So applying these results puts the relative order of those two suffixes as:

S[5,] == abado // Comes first (smaller)
S[1,] == abadabado

But abadabado < abado. I've been looking at this for a while, and can't seem to figure out where I stray from the algorithm.

I'm hoping someone with more experience using the algorithm can point me in the right direction.

  • 1
    $\begingroup$ $R$ in the paper "Linear Work Suffix Array Construction" refers to the concatenation of $R_1$ and $R_2$: [abb][ada][bba][do$][bba][dab][bad][o$$], this is different from your $R_{12}$. Are you referring to a different algorithm? $\endgroup$
    – pcpthm
    Dec 5, 2022 at 12:24
  • $\begingroup$ No you're absolutely right, and fixing that fixes my issue. Thanks a lot for pointing it out. $\endgroup$ Dec 5, 2022 at 13:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.