Наибольшая общая подпоследовательность [Оберон / Компонентный Паскаль / Вики]

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.

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

Данная реализация основана на [[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|реализации C++]].

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

<code componentpascal>

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.
</code>

Инструменты пользователя

Инструменты сайта

Инструменты страницы