Поиск в строках

{ **** UBPFD *********** by http://kladovka.net.ru/delphibase/ ****
>> Найти в двух строках самую длинную повторяющуюся подстроку (наивный алгоритм)

Функция, реализующая так называемый "наивный алгоритм" поиска наибольшей повторяющейся последовательности в двух строках. Алгоритм основан на матрице совпадений M размерности n х n. Матрица симметрична относительно диагонали.

Зависимости: Windows, SysUtils
Автор:       Vlad
Copyright:   http://www.webdelphi.ru/2009/07/poisk-v-strokax-naivnyj-algoritm-na-delphi/
Дата:        13 января 2010 г.
***************************************************************** }

function 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;

GetSequence('PABCQRABCSABTU', 'PABCQSDFRETYRT')=>PABCQ