Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Нахождение максимальной повторяющейся подстроки

Обозначения

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

Проект Delphi World © Выпуск 2002 - 2024
Автор проекта: USU Software
Вы можете выкупить этот проект.