i
<- t
-> n
-> n
-> u
-> m
e
r
a
с
y
Это представление действий по редактированию легко доступно для понимания, но при необходимости его можно развернуть. Как видите, наиболее длинная общая подпоследовательностью является (i, e, r, a, c, y), а определение удалений и вставок не представляет сложности.
Памятуя о том, что примененный метод является рекурсивным, следует подумать о требуемой для его реализации глубине стека. Если бы строки вообще не имели общих символов, последовательность редактирования сводилась бы к удалению всех символов первой строки и вставке всех символов второй строки. Если первая строка содержит n символов, а вторая m, глубина стека должна быть пропорциональной сумме n + m.
После того, как мы ознакомились с решением для двух строк, его можно модифицировать для вычисления LCS и генерации команд редактирования для двух текстовых файлов. Дабы упростить себе задачу, выполним считывание обоих файлов в объект TStringsLists. Понятно, что теперь одновременно выполняется сравнение целых текстовых строк, а не символов, тем не менее, в основном, реализация остается практически той же самой. Код интерфейса и вспомогательных методов приведен в листинге 12.27.
Листинг 12.27. Класс TtdFileLCS
type
TtdFileLCS = class private
FFromFile : TStringList;
FMatrix : TtdLCSMatrix;
FToFile : TStringList;
protected
function slGetCell(aFromInx, aToInx : integer): integer;
procedure slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
public
constructor Create(const aFromFile, aToFile : string);
destructor Destroy; override;
procedure WriteChanges(const aFileName : string);
end;
constructor TtdFileLCS.Create(const aFromFile, aToFile : string);
begin
{создать производный объект}
inherited Create;
{выполнить считывание файлов}
FFromFile := TStringList.Create;
FFromFile.LoadFromFile(aFromFile);
FToFile := TStringList.Create;
FToFile.LoadFromFile(aToFile);
{создать матрицу}
FMatrix := TtdLCSMatrix.Create(FFromFile.Count, FToFile.Count);
{заполнить матрицу}
slGetCell(pred(FFromFile.Count), pred(FToFile.Count));
end;
destructor TtdFileLCS.Destroy;
begin
{уничтожить матрицу}
FMatrix.Free;
{освободить списки строк}
FFromFile.Free;