Mercurial > lbo > hg > juliaplay
view julia/longest_common_subsequence.jl @ 6:661876a2502e
py: dp
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 12:50:44 +0100 |
parents | c1db337c15be |
children | 809f7d058647 |
line wrap: on
line source
function longest_common_subsequence(x::Vector{T}, y::Vector{T})::Vector{T} where {T} m, n = length(x), length(y) C = zeros(Int, m+1, n+1) # Not necessary: for i = 1:m C[i,1] = 0 end for j = 1:n C[1,j] = 0 end for i = 1:m for j = 1:n if x[i] == y[j] C[i+1,j+1] = C[i, j] + 1 else C[i+1,j+1] = max(C[i, j+1], C[i+1, j]) end end end # Reconstruct sequence i, j = m, n k = C[m+1, n+1] seq = Vector{T}(undef, k) while k > 0 if C[i,j] + 1 == C[i+1,j+1] seq[k] = x[i] k -= 1 i -= 1 j -= 1 elseif C[i,j+1] == C[i+1,j+1] i -= 1 elseif C[i+1,j] == C[i+1,j+1] j -= 1 end end seq end