Поиск в строках. Наивный алгоритм на 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)+1);
  for I:=0 to length(Matrix)-1 do
    SetLength(Matrix[i],length(str2)+1);
//строим матрицу
  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;

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

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

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

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