Обозначения

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 является самой длинной повторяющейся подстрокой.