# DC3/Skew Suffix Array Algorithm doesn't work for specific cases

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:

These are the triples of R12

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)

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.
• $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? Dec 5, 2022 at 12:24