Обозначения. 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 является самой длинной повторяющейся подстрокой. SpeedSIP значительно снижает расходы на телефонную связь и сервисы: бесплатные звонки внутри сети, выгодные международные и междугородные звонки, СМС по всему миру, покупка прямого номер любой страны, видеосвязь и видеоконференции. В этом разделе : 8  Наивный подход 8  Суффиксные деревья

8  Наивный подход 8  Суффиксные деревья