Delphi в Интернет, блог Delphi программистов

Эта статья будет полезна в первую очередь тем, кто часто имеет дело со сравнением и анализом строковых переменных. Также, думаю, что этот алгоритм смогут использовать в своей работе и люди, занимающиеся парсингом.

Цель: найти в двух строках самую длинную повторяющуюся подстроку.

< ' ' >

Для решения подобной задачи было разработано достаточно алгоритмов, каждый из которых имеет свои преимущества и недостатки. На мой взгляд, самым простым и эффективным является так называемый "наивный алгоритм".

1. Суть наивного алгоритма

Алгоритм основан на матрице совпадений M размерности n х n. Элементы этой матрицы определяются следующим образом:

Такая матрица симметрична относительно главной диагонали. Поэтому надо вычислить только элементы над ней или под ней. Диагонали из смежных ‘1’, за исключением главной, представляют повторения в строке y, там-то и нужно искать максимальные повторяющиеся подстроки. Вот пример матрицы совпадений для строки PABCQRABCSABTU.

Из приведенной выше матрицы можно видеть, что максимальными повторяющимися подстроками в данном примере являются ABC, с вхождениями y(2, 4) и y(7, 9), и AB, с вхождениями y(2, 3), y(7, 8) и y(11, 12). Легко выбрать более длинную из них, а именно, ABC.

Как уже упоминалось, поскольку матрица симметрична, достаточно вычислить элементы над главной диагональю, M(1...n-1,i+1...n), то есть всего n(n-1)/2 элементов. Таким образом, оценивание матрицы требует времени, пропорционального O(n²).

Уяснив для себя общие черты алгоритма, можно смело приступать к программированию. Я, не долго заморачиваясь, написал небольшую программку на Delphi, которая демонстрирует работу наивного алгоритма.

2. Наивный алгоритм в действии

Запускаем Delphi, создаем новый проект и укладываем на форму 2 Edit'а, 1 кнопку и 1 label. Должно получиться примерно следующее:

главная форма приложения

В Edit'ы будем вписывать анализируемые стоки и выводить в Label результат сравнения. Функция, реализующая работы наивного алгоритма выглядит следующим образом (с краткими комментариями):

function TForm1.GetSequence(str1, str2: string): string;
var i,j,max, max_i,max_j:integer;
Matrix: array of array of integer;
begin
//устанавливаем размерность массива
SetLength(Matrix, Length(str1));
for I:=0 to length(Matrix)-1 do
SetLength(Matrix[i],length(str2));
//строим матрицу
max:=0;
for i:=0 to length(Matrix)-1 do
for j:=0 to length(Matrix[i])-1 do
begin
if (i=0)or(j=0) then
Matrix[i,j]:=0
else
if str1[i]<>str2[j] then
Matrix[i,j]:=0
else
begin
Matrix[i,j]:=Matrix[i-1,j-1]+1;
if Matrix[i,j]>max then
begin
max:=Matrix[i,j];
max_i:=i;
max_j:=j;
end;
end;
end;
//Составляем строку по str1 i
result:='';
for I:=max_i-max+1 to max_i do
Result:=result+str1[i];
end;

Как видите, все достаточно просто. Берем один динамический массив, устанавливаем его размеры и, применяя формулу, представленную вышезаполняем массив нулями и единицами. В последнем цикле прозодимся по элементам и выбираем необходимую подстроку.

Результат работы программы представлен на рисунке:

Результат работы наивного алгоритма

Можно бесконечно долго совершенствовать алгоритмы поиска и анализа строк, но, на мой взгляд, наивный алгоритм наиболее подходящее решения для работы небольших программ. За сим откланиваюсь. Будут вопросы, пожелания - пишите :)

Мой блог находят по следующим фразам

• как работать без мышки в интернете
• защита темы wordpress от воровства
• программа для авторизации на сайте на дельфи
• Ribbon Delphi
• problem with check box in openoffice
• Как получить заголовок ответа сервера Delphi

Делись!	Загружай!	Плюсуй!
	Отправить PDF на

Комментарии (3)

• Рустам пишет:
  02 Июн 2011 в 11:03 дп

  В вашей реализации ошибка. Вы хоть тестировали её?

• Vlad пишет:
  02 Июн 2011 в 3:54 пп

  Тестировал на коротких строках, но это было уже давненько. В чем ошибка заключается?

• Рустам пишет:
  03 Июн 2011 в 4:44 пп

  Вход: ‘vlad’, ‘vl’. выход: ‘v’
  Вход: ‘vlad’, ‘vla’. выход: ‘vl’
  Теряет один символ.

  Правильно:
  …
  SetLength(Matrix, Length(str1)+1);
  for I:=0 to length(Matrix)-1 do
  SetLength(Matrix[i],length(str2)+1);
  …

Ваш ответ