Таблица 12.1. Матрица LCS для строк BEGIN и FINISH
_ _ F I N I S H
_ 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0
G 0 0 0 0 0 0 0
I 0 0 1 1 1 1 1
N 0 0 1 2 2 2 2
Записать этот процесс выполнения действий вручную в виде кода не особенно трудно. Чтобы облегчить задачу начинающим программистам, я решил вначале создать класс матричного кеша. Внутри этого класса матрица хранится в объекте TList из TLists, причем ведущий объект TList представляет строки в матрице, а ведомый TLists - ячейки в столбцах отдельной строки. Кроме того, класс матрицы специфичен для решаемой задачи. Было бы излишним разрабатывать, кодировать и использовать общий класс матрицы. Код реализации класса матрицы показан в листинге 12.22.
Листинг 12.22. Класс матрицы для реализации алгоритма определения LCS
type
TtdLCSDir = (ldNorth, ldNorthWest, ldWest);
PtdLCSData = ^TtdLCSData;
TtdLCSData = packed record
ldLen : integer;
ldPrev : TtdLCSDir;
end;
type
TtdLCSMatrix = class private
FCols : integer;
FMatrix : TList;
FRows : integer;
protected
function mxGetItem(aRow, aCol : integer): PtdLCSData;
procedure mxSetItem(aRow, aCol : integer;
aValue : PtdLCSData);
public
constructor Create(aRowCount, aColCount : integer);
destructor Destroy; override;
procedure Clear;
property Items [aRow, aCol : integer] : PtdLCSData
read mxGetItem write mxSetItem;
default;
property RowCount : integer read FRows;
property ColCount : integer read FCols;
end;
constructor TtdLCSMatrix.Create(aRowCount, aColCount : integer);
var
Row : integer;
ColList : TList;
begin
{создать производный объект}
inherited Create;
{выполнить простую проверку}
Assert ((aRowCount > 0) and (aColCount > 0),
' TtdLCSMatrix.Create: Invalid Row or column count');
FRows := aRowCount;
FCols := aColCount;
{создать матрицу: она будет матрицей TList матриц TLists, упорядоченных по строкам}