Почему LCS алгоритм находит совпадение в конце последовательности?

Спасибо большое, всё получилось.

Почему LCS алгоритм находит совпадение в конце последовательности?

Что касается полной задачи, то мне надо именно что найти фрагмент текста в начале большого куска текста. Сравнение нечёткое, потому что большой кусок — это распознанный из картинки текст и нужно найти соответствие его и уже существующего.

Почему LCS алгоритм находит совпадение в конце последовательности?

Мне рекурсию надо как-то «снизу» запускать...

Почему LCS алгоритм находит совпадение в конце последовательности?

Wataru, там рекурсия. Сначала я строю матрицу:

// строим матрицу
  for I := 0 to aCountLeft-1 do
  begin
   for J := 0 to aCountRight-1 do
   begin
    if aCompareFunc(I,J) then
     PutAt(I,J, GetAt(I-1, J-1) + 1)
    else
     PutAt(I,J, Max(GetAt(I, J-1), GetAt(I-1, J)));
   end;
  end;

А потом строю diff:

procedure DoDiff(aL, aR: Integer);
 begin
  if (aL >= 0) and (aR >= 0) and aCompareFunc(aL, aR) then
  begin
   DoDiff(aL-1, aR-1);
   aReportProc(RR(l3diffSame, aL, aR));
  end
  else
   if (aR >= 0) and ((aL < 0) or (GetAt(aL, aR-1) >= GetAt(aL-1, aR))) then
   begin
    DoDiff(aL, aR-1);
    aReportProc(RR(l3diffAdded, aL, aR));
   end
   else
    if (aL >= 0) and ((aR < 0) or (GetAt(aL, aR-1) < GetAt(aL-1, aR))) then
    begin
     DoDiff(aL-1, aR);
     aReportProc(RR(l3diffDeleted, aL, aR));
    end;
 end;

Почему LCS алгоритм находит совпадение в конце последовательности?

Wataru, мне надо, чтобы находил совпадение в начале. Для решения прикладной задачи. Если находит в конце, это ломает мне алгоритм. Попытаюсь разобраться.

Алгоритм сопоставления двух текстов?

Спасибо всем ответившим. Дифф, конечно, идеально, но там диффер сдохнет, если сравнивать даже пословно, тексты довольно большие. А разделение по параграфам и строкам может быть разным, так что их сравнивать тоже не вариант.

Поэтому я пришёл к решению, когда я нормализую текст, удаляя знаки препинания и прочие незначащие символы, а затем итеративно сворачиваю в хеши сначала слова, а потом и сочетания слов-хешей. И сравниваю на каждом уровне, находя различающиеся фрагменты и уточняя сравнение. В итоге можно и до символов дойти, если надо. Но мне достаточно по словам сравнить.

Ещё раз спасибо.

Алгоритм сопоставления двух текстов?

shurshur, ну вот я думал уже в этом направлении. Но как мне, например, сделать своего рода «нечёткий хэш» предложения? Так чтобы если, скажем в одном из текстов слово не распозналось толком, то соответствие предложений всё равно было найдено...