Изменения
→Упрощенный алгоритм
Будем вычислять все повторяющиеся подстроки длины <tex>l</tex> для всех <tex>l</tex>, где таких что <tex>1 \leqslant l = 1 \ldots leqslant n - 1</tex>. Зная эти данные, мы автоматически находим все тандемные повторы.
Предположим, что в строке <tex>f_6</tex> вычислены последовательности позиций, в которых встречаются одинаковые символы:
|}
Если нам заранее известен алфавит , и он индексирован, то мы можем выполнить данное вычисление за <tex>O(n)</tex>.
Далее для <tex>l = 2</tex> мы хотим найти все повторяющиеся подстроки длины <tex>2</tex>. Поскольку повторяющиеся подстроки длины <tex>l \geqslant 2</tex> будут иметь общий префикс длиной <tex>l - 1</tex>, то вычисления уровня <tex>l</tex> должны привести к последовательностям, которые будут подпоследовательностями последовательностей, вычисленных на уровне <tex>l - 1</tex>. Другими словами, разбиение на уровне <tex>l \geqslant 2</tex> {{---}} декомпозиция разбиения на уровне <tex>l - 1</tex>:
