Алгоритмы: Математика, Сортировка, Поиск, Игры и все с ними связанное, Графика, Сжатие и защита информации и многое другое. Поиск в строках, массивах, последовательностях: Общие подпоследовательности, дистанция.

Cтрока x длины |x| = m записывается как x₁x₂ ... x_m, где x_i представляет i-й символ x.

Подстрока x_ix_i+1 ... x_j строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная подстрока обозначается так x_R(i,j).

Обычно x будет обозначать искомый образец, а y – текстовую строку; |x| = m, |y| = m и, конечно, m<=n.

Задача нахождения самой длинной подстроки (longest repeated substring), появляющейся в данной строке более одного раза, можно сформулировать следующим образом.

Максимальная повторяющаяся подстрока – это подстрока, имеющая в данной строке не меньше двух различных вхождений, причем сопоставление нельзя продолжить ни в одном направлении. Рассмотрим, например, строку PABCQRABCSABTU. Подстроки A, B, C, AB, BC и ABC повторяются. Строки AB и ABC являются максимальными повторяющимися подстроками, и, таким образом, ABC является самой длинной повторяющейся подстрокой.

Наивный подход к решению этой задачи, которому требуется квадратичное время, состоит в следующем. Строится матрица M размерности n * n, такая что M_i,j = 1 если y_i = y_j, и M_i,j = 0 в противном случае. За исключением главной диагонали, все диагонали в матрице, состоящие из идущих подряд `1’, представляют максимальные повторяющиеся подстроки, самая длинная из которых является, таким образом, самой длинной повторяющейся подстрокой. Обратите внимание, что матрица симметрична относительно главной диагонали, поэтому достаточно вычислять и обрабатывать только одну, скажем, верхнюю, ее половину (то есть элементы M_{1...n-1,i+1...n+1}).

Поиск в строках, массивах, последовательностях: Максимальная повторяющаяся подстрока.

Обозначения.