Mercurial > lbo > hg > juliaplay
view julia/longest_common_subsequence.jl @ 8:809f7d058647
Some more dp problems
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 15:17:09 +0100 |
parents | c1db337c15be |
children | cb419167dcb3 |
line wrap: on
line source
function lcss_len(x::Vector{T}, y::Vector{T}, i=1, j=1, a=nothing) where {T} a = isnothing(a) ? zeros(T, min(length(x), length(y))) : a if i > length(x) || j > length(y) 0 elseif x[i] == y[j] n = 1 + lcss_len(x, y, i+1, j+1, a) a[n] = x[i] n else max(lcss_len(x, y, i+1, j, a), lcss_len(x, y, i, j+1, a)) end end function lcss_diff(x::Vector{T}, y::Vector{T}) where {T} lcss = longest_common_subsequence(x, y) i, j, k = 1, 1, 1 while i <= length(lcss) && j <= length(x) && k <= length(y) if x[j] == lcss[i] && y[k] == lcss[i] i += 1 j += 1 k += 1 elseif x[j] == lcss[i] && y[k] != lcss[i] println("Added: $i $(y[k])") k += 1 elseif y[k] == lcss[i] && x[j] != lcss[i] println("Removed: $i $(x[j])") j += 1 else println("Changed: $(x[j]) -> $(y[k])") j += 1 k += 1 end end end function lrss_len(x::Vector{T}, i=1, j=1) where {T} if max(i, j) > length(x) 0 elseif x[i] == x[j] && i != j 1 + lrss_len(x, i+1, j+1) else max(lrss_len(x, i+1, j), lrss_len(x, i, j+1)) end end # This has a bug: e.g. [1,2,3,4,5,6] vs [1,2,4,5,6]. Sequences need to have same length 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