Изменения

На этом шаге строится суффиксные массивы суффиксный массив <tex> A_{S_1S_{12} </tex> и <tex> A{S_2} </tex> для множества суффиксов <tex> \{ S[i..n-1] | i \mod 3 \ne 0 \} </tex>.

#* Перекодируем строку <tex> S </tex> в строку <tex> S' </tex> длиной <tex> \frac23 n </tex> в алфавите <tex> \Sigma' </tex> следущим образом: <tex> S' = [ \Sigma'(s[i..i+2]) | i \mod 3 == 1 ] + [ \Sigma'(s[i..i+2]) | i \mod 3 == 2 ] </tex>. Как можно заметить, длиной строки <tex> S' </tex> будет <tex> n' = \frac23 n </tex>. Суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \mod 3 == 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i \mod 3 == 2 </tex>, то строка <tex> S'[\frac{n}{3} + \frac{i-2}{3}..\frac{2n}{3} - 1] </tex>.

# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j </tex>, где <tex> j \mod 3 == 3A_{S'}[i] + 1 </tex>, тогда добавим в массив строке <tex> A_{S_1} </tex> значение <tex> 3A_{S'}[i] + 1 </tex>. Если , если же <tex> A_{S'}[i] \ge \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j </tex>, где <tex> j \mod 3 == 2 </tex>, тогда добавим в массив <tex> A_{S_2} </tex> значение <tex> 3(A_{S'}[i] - \frac{n}{3}) + 2 </tex> в строке <tex> S </tex>. Псевдокод этого шага: получения <tex> A_{S_1S_{12}} </tex> = []: <tex> A_{S_2S_{12}} </tex> = [] for i = 0..<tex>A_{S'}</tex>.length- 1:

<tex>A_{S_1S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)

<tex>A_{S_2S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n / 3) + 2)