Изменения
→Оптимизация
Таким образом, декомпозицию на уровне <tex>l + 1</tex> можно выполнить косвенным путем, рассматривая каждую последовательность уровня <tex>l</tex> с позиции, находящейся на <tex>1</tex> левее от начальной позиции этой последовательности.
{{Лемма
|statement=В каждом наборе последовательностей, порожденных одной последовательностью уровня <tex>l - 1</tex>, всегда можно исключить использование одной из них для декомпозиции последовательностей на уровне <tex>l</tex>
|proof=TBA
}}
{{Определение
В декомпозиции последовательности <tex>c^l_j</tex> на последовательности <tex>(c^{l+1}_1, c^{l+1}_2, \ldots, c^{l+1}_q), q \geqslant 1 </tex> назовем одну последовательность с наибольшим количеством элементов '''большой''', а остальные <tex>q - 1</tex> последовательности - '''малыми'''. Для <tex>l = 1</tex> все последовательности будем считать '''малыми'''.
}}
{{Лемма|statement=Предположим, что декомпозиция последовательностей, соответствующих произвольной строке <tex>s[1..n]</tex>, выполняется для уровней <tex>l = 1, 2, \ldots, l^*</tex>, где <tex>l^*</tex> {{---}} наименьший уровень, на котором каждая последовательность содержит единственную позицию. Тогда каждая позиция <tex>i</tex> строки <tex>s</tex> входит в малые последовательности <tex>O(\log n)</tex> раз|proof=TBA}} Поскольку строка <tex>s</tex> содержит <tex>n</tex> позиций, то из предыдущей леммы следует, что всего в малых последовательностях на всех уровнях содержится <tex>O(n \log n)</tex> позиций. Таким образом, если время обработки последовательностей на каждом уровне <tex>l</tex> пропорционально количеству элементов в малых последовательностях этого уровня, то полный процесс декомпозиции будет выполнен за <tex>O(n \log n)</tex>, чего мы и хотели получить.
= Псевдокод =
