Standard algorithm for longest common subsequence in Julia.

lcss.jl

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