Изменения

Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, работающий за <tex>O(n^2)</tex>\, а затем попытаемся его оптимизировать, в итоге придя к нужному нам результатудо <tex>O(n \cdot log(n))</tex>.

{|class="wikitable" style="text-align:center" |-

 Будем вычислять все повторяющиеся подстроки длиной <tex>l</tex>, где <tex>l = 1 \ldots n - 1</tex>.Предположим, что в строке <tex>f_6</tex> вычислены последовательности позиций, в которых встречаются одинаковые символы:{|class="wikitable" style="text-align:center" |- |rowspan="2"| <tex>l = 1</tex> || <1, 3, 4, 6, 8, 9, 11, 12> || <2, 5, 7, 10, 13> |- || a || b |} Если нам заранее известен алфавит и он индексирован, то мы можем выполнить данное вычисление за <tex>O(n)</tex>. Далее для <tex>l = 2</tex> мы хотим найти все повторяющиеся подстроки длины <tex>2</tex>.Поскольку повторяющиеся подстроки длины <tex>l \geq 2</tex> будут иметь общий префикс длиной <tex>l - 1</tex>, то вычисления уровня <tex>l</tex> должны привести к последовательностям, которые будут подпоследовательностями последовательностей, вычисленных на уровне <tex>l - 1</tex>. n Другими словами, разбиение на уровне <tex>l \geq 2</tex> {{---}} декомпозиция разбиения на уровне <tex>l - 1</tex>: {|class="wikitable" style="text-align:center" !colspan=6|Последовательная декомпозиция строки <tex>f_6 = abaababaabaab</tex> |- | rowspan="2" | <tex>l = 2</tex> || <1, 4, 6, 9, 12> || <3, 8, 11> || <2, 5, 7, 10> || <13> || |- || ab || aa || ba || b$ |||- | rowspan="2" | <tex>l = 3</tex> || <1, 4, 6, 9> || <12> || <3, 8, 11> || <2, 7, 10> || <5> |- || aba || aa$ || aab || baa || bab|- | rowspan="2" | <tex>l = 4</tex> || <1, 6, 9> || <4> || <3, 8> || <11> || <2, 7, 10> |- || abaa || abab || aaba || aab$ || baab|- | rowspan="2" | <tex>l = 5</tex>|| <1, (здесь и далее 6, 9> || <3> || <8> || <2, 7> || <10> |- || abaab || aabab || aabaa || baaba || baab$|- | rowspan="2" | <tex>n l = 6</tex> |s|<1, 6> || <9> || <2> || <7> || |- || abaaba || abaab$ || baabab || baabaa |||- | rowspan="2" | <tex>l = 7</tex>|| <1> || <6> || || || |- || abaabab || abaabaa || || || |} Если реализовывать процесс декомпозиции "наивно", то поучаем сложность <tex>O(n^2)</tex>. == Оптимизация ==