longest-subseq ( seq1 seq2 -- subseq )

Vocabulary

sequences.extras

Inputs

seq1	a sequence
seq2	a sequence

Outputs

subseq

an object

Word description

Pushes the longest subsequence of seq.

Definition

USING: arrays kernel math ranges sequences sequences.private ;

IN: sequences.extras

:: longest-subseq ( seq1 seq2 -- subseq )
    seq1 length :> len1 seq2 length :> len2 0 :> n! 0 :> end!
    len1 1 + [ len2 1 + 0 <array> ] replicate
    :> table len1 [0..b) [| x |
        x seq1 nth-unsafe :> elt1 x 1 + table nth-unsafe
        :> tab1 len2 [0..b) [| y |
            elt1 y seq2 nth-unsafe = [
                y x table nth-unsafe nth-unsafe 1 +
                :> len len y 1 + tab1 set-nth-unsafe len n >
                [ len n! x 1 + end! ] when
            ] [ 0 y 1 + tab1 set-nth-unsafe ] if
        ] each
    ] each end n - end seq1 subseq ;