===== Наибольшая общая подпоследовательность =====
==== Компонентный Паскаль ====
Данная реализация основана на реализации C++ с [[http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C|Наибольшая общая подпоследовательность]]. Отличие состоит в том, что вместо строки возвращаются начальная позиция подстроки в строке //a// и её длина.
(* Longest Common Substring (LCS) *)
PROCEDURE FindLCS* (IN a, b: ARRAY OF CHAR; OUT start, len: INTEGER);
VAR
max_len: POINTER TO ARRAY OF ARRAY OF INTEGER;
i, j, alen, blen: INTEGER;
on: BOOLEAN;
BEGIN
alen := LEN(a$);
blen := LEN(b$);
(* Important: we use arrays of size (|A|+1) x (|B|+1) *)
NEW(max_len, alen + 1, blen + 1);
FOR i := alen - 1 TO 0 BY -1 DO
FOR j := blen - 1 TO 0 BY -1 DO
IF a[i] = b[j] THEN
max_len[i, j] := 1 + max_len[i + 1, j + 1]
ELSE
max_len[i, j] := MAX(max_len[i + 1, j], max_len[i, j + 1])
END
END
END;
i := 0; j := 0; len := 0; on := FALSE;
WHILE (max_len[i, j] # 0) & (i < alen) & (j < blen) DO
IF a[i] = b[j] THEN
IF ~on THEN
on := TRUE; start := i
END;
INC(len);
INC(i);
INC(j)
ELSIF max_len[i, j] = max_len[i + 1, j] THEN
INC(i)
ELSE
INC(j)
END
END
END FindLCS;
=== Пример использования ===
PROCEDURE Do*;
VAR
start, len: INTEGER;
s1, s2, s: ARRAY 128 OF CHAR;
BEGIN
s1 := "sccdeffou";
s2 := "hrtfjjcdefy";
FindLCS(s1, s2, start, len);
Strings.Extract(s1, start, len, s);
Log.String("Longest common substring: " + s); Log.Ln
END Do;
==== Внешние ссылки ====
* [[http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C|Наибольшая общая подпоследовательность]]
==== Авторы реализации ====
* Компонентный Паскаль: //Роман М.//