longest-subseq ( seq1 seq2 -- subseq )


Vocabulary
sequences.extras

Inputs
seq1a sequence
seq2a sequence


Outputs
subseqan object


Word description
Pushes the longest subsequence of seq.

Definition


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