0123456789ABCDE una_banana_nana Assumption: $ < _ < a < b < ... < z =============== Step 1 ================ mod 3 = 1 | mod 3 = 2 1 4 7 A | 2 5 8 B $ starting position (mod 3 != 0) na_ ban ana _na na$ | a_b ana na_ nan a$$ _na a$$ a_b ana ban na$ na_ nan sorted triples 1 2 3 4 5 6 7 8 lexicographic names mod 3 = 1 | mod 3 = 2 na_ ban ana _na na$ | a_b ana na_ nan a$$ 7 5 4 1 6 | 3 4 7 8 2 lexicographic names s^{12} = 7 5 4 1 6 | 3 4 7 8 2 lexicographic names SA^{12} = 3 9 5 2 6 1 4 0 7 8 Suffix Array of s^{12} Example: SA^{12}[3] = 2 = 416|34782 = ana_nana$|a_banana_nana _______________ ignore this Because 2 < (E+1)/3 = 5, 2 is a suffix starting at 2*3+1 = 7 Indeed, S[7] = ana_nana Example: SA^{12}[4] = 6 = 4782 = anana_nana$$ __ ignore this Because 6 >= (E+1)/3 = 5, 6 is a suffix starting at (6-5)*3+2 = 5 Indeed, S[5] = anana_nana Moreover, 3 < 4 and thus S[7,..] < S[5,..]. Indeed ana_nana < anana_nana. SA^{12} = 3 9 5 2 6 1 4 0 7 8 Suffix Array of s^{12} SA_{12} = A E 2 7 5 4 D 1 8 B Suffix Array of S excluding the positions multiple of 3 To obtain SA from SA^{12} use the same formula used in the examples above. =============== Step 2 ================ 0123456789ABCDE una_banana_nana mod 3 = 0 0 3 6 9 C una_banana_nana 0 3 6 9 C u1 _4 n7 aA cD suffixes that start at i mod 3 = 0 _4 aA cD n7 u1 sorted suffixes that start at i mod 3 = 0 3 9 C 6 0 [ if we had e.g. aA a4 as two suffixes, we would have put aA < a4 because A < 4 in SA ] SA_0 = 3 9 C 6 0 Suffix Array of S including only the positions multiple of 3 =============== Step 3 ================ 0123456789ABCDE una_banana_nana SA_0 = 3 9 C 6 0 Suffix Array of S including only the positions multiple of 3 SA_{12} = A E 2 7 5 4 D 1 8 B Suffix Array of S excluding the positions multiple of 3 Merge(SA_0, SA_{12}): Merge(39C60, AE2754D18B) 3 vs A _banana_nana vs _nana A mod 3 = 1 _4 vs _B 4 < B in SA_{12} ==> 3 = _4 < _B = A ** ouput: 3 ** Merge(9C60, AE2754D18B) 9 vs A A mod 3 = 1 aA vs _B _ < a ** output: A ** Merge(9C60, E2754D18B) 9 vs E E last char, followed by empty string aA vs a < A ===> a = E < aA = 9 ** output: E ** Merge(9C60, 2754D18B) 9 vs 2 2 mod 3 = 2 a_B vs a_4 4 < B in SA_{12} ==> 2 = a_4 < a_B = 9 ** output: 2 ** Merge(9C60, 754D18B) ............. Final output: SA = Merge(SA_0, SA_{12}) = 3AE29C754D18B60 Indeed: 0123456789ABCDE una_banana_nana SA 3 _banana_nana A _nana E a 2 a_banana_nana 9 a_nana C ana 7 ana_nana 5 anana_nana 4 banana_nana D na 1 na_banana_nana 8 na_nana B nana 6 nana_nana 0 una_banana_nana