|
Cтрока x длины |x| = m записывается как x1x2 ... xm, где xi представляет i-й символ x.
Подстрока xixi+1 ... xj строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная
подстрока обозначается так xR(i,j).
Обычно x будет обозначать искомый образец, а y – текстовую строку; |x| = m, |y| = m и, конечно, m<=n.
Пример:
x = trismegistus
|x| = 12
x(7,10) = gist
xR(7,4) = gems
Задача нахождения самой длинной подстроки (longest repeated substring), появляющейся в данной строке более одного раза, можно сформулировать следующим образом.
Для данной строки y, |y| = n > 0, найти самую длинную подстроку, встречающуюся в y больше одного раза.
Cамая длинная повторяющаяся подстрока – это самая длинная из строк максимальной длины x, такая что y = uxvxw для некоторых строк u, v и w, где |u| > 0, |v| > 0 и |w| > 0.
Максимальная повторяющаяся подстрока – это подстрока, имеющая в данной строке не меньше двух различных вхождений, причем сопоставление нельзя продолжить ни в одном направлении. Рассмотрим, например, строку PABCQRABCSABTU. Подстроки A, B, C, AB, BC и ABC повторяются. Строки AB и ABC являются максимальными повторяющимися подстроками, и, таким образом, ABC является самой длинной повторяющейся подстрокой.
| | 
| Наивный подход
Наивный подход к решению этой задачи, которому требуется квадратичное время, состоит в следующем. Строится матрица M размерности n * n, такая что Mi,j = 1 если yi = yj, и Mi,j = 0 в противном случае. За исключением главной диагонали, все диагонали в матрице, состоящие из идущих подряд `1', представляют максимальные повторяющиеся подстроки, самая длинная из которых является, таким образом, самой длинной повторяющейся подстрокой. Обратите внимание, что матрица симметрична относительно главной диагонали, поэтому достаточно вычислять и обрабатывать только одну, скажем, верхнюю, ее половину (то есть элементы M1...n-1,i+1...n+1).
|
| Суффиксные деревья
Более сложный и эффективный алгоритм.
|
|
