Наибольшая общая подпоследовательность

Данная реализация основана на реализации C++.

Отличие состоит в том, что вместо строки возвращаются начальная позиция подстроки в строке a и её длина.

MODULE DemoLCS;
 
IMPORT Log, Strings;
 
(* 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;
 
END DemoLCS.