Изменения
→Шаг 3
<tex>A_{S}</tex> = []
// Вначале предподсчитаем за O(n) обратные перестановки обратную перестановку для суффиксных массивовсуффиксного массива <tex> A_{S_{12}}</tex>, то есть массивы массив rank такиетакой, что A<tex> A_{S_{12}}</tex>[rank[i]] = i.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
while i < 2 * n / 3 and j < n / 3:
pos12 = <tex> A_{S_{12}} </tex>[i]
pos0 = <tex> A_{0} </tex>[j]
if pos12 % 3 == 1:
if Pair(S[pos12], rank12rank[pos12 + 1]) < Pair(S[pos0], rank0rank[pos0 + 1]):
<tex>A_{S}</tex>.add(pos12)
i++
j++
else:
if Triple(S[pos12], S[pos12 + 1], rank12rank[pos12 + 2]) < Triple(S[pos0], S[pos0 + 1], rank12rank[pos0 + 2]):
<tex>A_{S}</tex>.add(pos12)
i++
