Алгоритм Крочемора

Определение:

Тандемным повтором (tandem repeat) в строке называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов [math]i \lt j[/math] такими, что подстрока [math]s[i \ldots j][/math] — это две одинаковые строки, записанные подряд.

Алгоритм Крочемора (Crochemore algorithm) позволяет найти все тандемные повторы в исходной строке [math]s[1..n][/math] за [math]O(n \cdot log (n))[/math].

Идея

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

Упрощенный алгоритм

Рассмотрим следующую строку Фиббоначи:

	1	2	3	4	5	6	7	8	9	10	11	12	13
[math]f_6 = [/math]	a	b	a	a	b	a	b	a	a	b	a	a	b

Будем вычислять все повторяющиеся подстроки длиной [math]l[/math], где [math]l = 1 \ldots n - 1[/math]. Предположим, что в строке [math]f_6[/math] вычислены последовательности позиций, в которых встречаются одинаковые символы:

[math]l = 1[/math]	<1, 3, 4, 6, 8, 9, 11, 12>	<2, 5, 7, 10, 13>
	a	b

Если нам заранее известен алфавит и он индексирован, то мы можем выполнить данное вычисление за [math]O(n)[/math].

Далее для [math]l = 2[/math] мы хотим найти все повторяющиеся подстроки длины [math]2[/math]. Поскольку повторяющиеся подстроки длины [math]l \geq 2[/math] будут иметь общий префикс длиной [math]l - 1[/math], то вычисления уровня [math]l[/math] должны привести к последовательностям, которые будут подпоследовательностями последовательностей, вычисленных на уровне [math]l - 1[/math]. Другими словами, разбиение на уровне [math]l \geq 2[/math] — декомпозиция разбиения на уровне [math]l - 1[/math]:

Последовательная декомпозиция строки [math]f_6 = abaababaabaab[/math]
[math]l = 2[/math]	<1, 4, 6, 9, 12>	<3, 8, 11>	<2, 5, 7, 10>	<13>
	ab	aa	ba	b$
[math]l = 3[/math]	<1, 4, 6, 9>	<12>	<3, 8, 11>	<2, 7, 10>	<5>
	aba	aa$	aab	baa	bab
[math]l = 4[/math]	<1, 6, 9>	<4>	<3, 8>	<11>	<2, 7, 10>
	abaa	abab	aaba	aab$	baab
[math]l = 5[/math]	<1, 6, 9>	<3>	<8>	<2, 7>	<10>
	abaab	aabab	aabaa	baaba	baab$
[math]l = 6[/math]	<1, 6>	<9>	<2>	<7>
	abaaba	abaab$	baabab	baabaa
[math]l = 7[/math]	<1>	<6>
	abaabab	abaabaa

Если реализовывать процесс декомпозиции "наивно", то поучаем сложность [math]O(n^2)[/math].