Skip to content

Instantly share code, notes, and snippets.

@dermesser

dermesser/lcss.jl

Created November 13, 2022 17:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dermesser/8be4da21c56f1568525f2f68dd732a39 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dermesser/8be4da21c56f1568525f2f68dd732a39 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dermesser created this gist Nov 13, 2022.
    38 changes: 38 additions & 0 deletions lcss.jl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,38 @@
    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