Изменения

Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем:

на каждом уровне <tex>l</tex> выполняется непосредственная декомпозиция каждой последовательности <tex>c^{l}_j</tex>. Более точно, если <tex>c^{l}_j = \langle p_1, p_2, \ldots , p_r \rangle</tex>, то необходимо проверить совпадение букв <tex>s[p_1 + l], s[p_2 + l], \ldots, s[p_r + l]</tex>, и, если какие-либо пары букв <tex>s[p_i + l]</tex> и <tex>s[p_j + l]</tex> равны, то <tex>p_i</tex> и <tex>p_j</tex> помещаются в одну и ту же последовательность на уровне <tex>l + 1</tex>.

Заметим, что декомпозицию можно выполнить, основываясь не на разбиваемой последовательности, а на последовательностях, относительно которых будут разбиваться другие последовательности.

Для каждой позиции <tex>p_i > 1</tex> известно, что подстрока <tex>s[p_i - 1 \ldots p_i + l - 1]</tex> (длиной <tex>l + 1</tex>) относится к некоторой последовательности <tex>c^{l + 1}_{j'}</tex> на уровне <tex>l + 1</tex>. Поскольку последовательность <tex>c^{l}_{j}</tex> соответствует уникальной подстроке строки <tex>s</tex>, то каждая такая последовательность <tex>c^{l + 1}_{j'}</tex> должна формироваться из тех же позиций <tex>p_{i_1}, p_{i_2}, \ldots , p_{i_k}</tex> последовательности <tex>c^{l}_{j}</tex>, которые определяют класс эквивалентности

<tex>s[p_{i_1} - 1] = s[p_{i_2} - 1] = \ldots = s[p_{i_k} - 1]</tex>.

Таким образом, декомпозицию на уровне <tex>l + 1</tex> можно выполнить косвенным путем, рассматривая каждую последовательность уровня <tex>l</tex> с позиции, находящейся на <tex>1</tex> левее от начальной позиции этой последовательности.

{{Лемма

Заметим, что если последовательность <tex>c^l_j</tex> разбивается на подпоследовательности <tex>(c^{l+1}_1, c^{l+1}_2, \ldots, c^{l+1}_q)</tex>, то каждая малая последовательность <tex>c^{l+1}_{j'}</tex> удовлетворяет условию <tex>c^{l+1}_{j'} \leqslant {c^{l}_{j} \over 2}</tex>. Другими словами, при <tex>l \geqslant 2</tex> каждая малая последовательность не превышает половины размера своей исходной последовательности. Поскольку для <tex>l - 1</tex> начальная малая последовательность может содержать не более n позиций, то из этого следует, что ни одна из позиций не может входить в больше, чем <tex>\log_2(n+1)</tex> малых последовательностей.

}}

Поскольку строка <tex>s</tex> содержит <tex>n</tex> позиций, то из предыдущей леммы следует, что всего в малых последовательностях на всех уровнях содержится <tex>O(n \log n)</tex> позиций. Таким образом, если время обработки последовательностей на каждом уровне <tex>l</tex> пропорционально количеству элементов в малых последовательностях этого уровня, то полный процесс декомпозиции будет выполнен за <tex>O(n \log n)</tex>, чего мы и хотели получить.