Изменения
Нет описания правки
}}
'''Алгоритм Крочемора''' (Crochemore algorithm) позволяет найти все тандемные повторы в исходной строке <tex>s[1..n]</tex> за <tex>O(n \cdot log (n))</tex>.
= Идея =
Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, работающий за <tex>O(n^2)</tex>\, а затем попытаемся его оптимизировать до <tex>O(n \cdot log(n))</tex>.
== Упрощенный алгоритм ==
|}
Если реализовывать процесс декомпозиции "наивно", то поучаем сложность <tex>O(n^2)</tex>.
== Оптимизация ==
Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем:
на каждом уровне <tex>l</tex> выполняется непосредственная декомпозиция каждой последовательности <tex>c^{(l)}_j</tex>. Более точно, если <tex>c^{(l)}_j = <p_1, p_2, \ldots , p_r></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>f_6</tex> последовательность <tex><1, 4, 6, 9></tex> на уровне <tex>3</tex> разбивается на уровне <tex>4</tex> на последовательности <tex><1, 6, 9></tex> и <tex><4></tex>, поскольку
<tex>f_6[1 + 3] = f_6[6 + 3] = f_6[9 + 3] \neq f_6[4 + ]</tex>.
Но декомпозицию можно выполнить, основываясь не на разбиваемой последовательности, а на последовательностях, относительно которых будут разбиваться другие последовательности. Снова рассмотрим уровень <tex>l = </tex> и последовательность
<tex>c^{(3)}_1 = <p_1, p_2, p_3, p_4> = <1, 4, 6, 9></tex>,
относящуюся к подстроке <tex>aba</tex>.
= Псевдокод =
