Search code examples
stringalgorithmdata-structuressuffix-arrayarray-algorithms

Meaning of S[3i]S[3i + 1]S[3i + 2]

I have trouble understanding the following:
We have the String ABRACADABRA. We divide this into groups as example: S is divided into the group:

S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...> where <> signifies an array and S[i] signifies the character in S in the position i.

I was expecting that S0=<S[0]S[4]S[8]S[11]> but according to the "solution" in the book I read it is not as S0=[ABR][ACA][DAB][RA] which is essentially S[0]S[3]S[6]S[9].
So what am I reading wrong in the formula S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...>?

In case it matters it is from a chapter I read on Suffix Arrays. I only have trouble in the formula

Solution

  • S0=[ABR][ACA][DAB][RA] is not S[0]S[3]S[6]S[9]. S[0]S[3]S[6]S[9] would be AADR.

    This is what happens:

    For i=0:
    <S[3i]S[3i+1]S[3i+2]> = <S[3*0]S[3*0+1]S[3*0+2]> = <S[0]S[1]S[2]> = <ABR>

    For i=1:
    <S[3i]S[3i+1]S[3i+2]> = <S[3*1]S[3*1+1]S[3*1+2]> = <S[3]S[4]S[5]> = <ACA>

    For i=2:
    <S[3i]S[3i+1]S[3i+2]> = <S[3*2]S[3*2+1]S[3*2+2]> = <S[6]S[7]S[8]> = <DAB>

    For i=3:
    <S[3i]S[3i+1]S[3i+2]> = <S[3*3]S[3*3+1]S[3*3+2]> = <S[9]S[10]S[11]> = <RA >