Anonymous user
Longest common subsequence: Difference between revisions
Added Julia language
m (→{{header|C++}}) |
(Added Julia language) |
||
Line 1,589:
"1234"
"tsitest"</lang>
=={{header|Julia}}==
<lang julia># v0.6
longest(a::String, b::String) = length(a) ≥ length(b) ? a : b
"""
julia> lcsrecursive("thisisatest", "testing123testing")
"tsitest"
"""
# Recursive
function lcsrecursive(xstr::String, ystr::String)
if length(xstr) == 0 || length(ystr) == 0
return ""
end
x, xs, y, ys = xstr[1], xstr[2:end], ystr[1], ystr[2:end]
if x == y
return string(x, lcsrecursive(xs, ys))
else
return longest(lcsrecursive(xstr, ys), lcsrecursive(xs, ystr))
end
end
# Dynamic
function lcsdynamic(a::String, b::String)
lengths = zeros(Int, length(a) + 1, length(b) + 1)
# row 0 and column 0 are initialized to 0 already
for (i, x) in enumerate(a), (j, y) in enumerate(b)
if x == y
lengths[i+1, j+1] = lengths[i, j] + 1
else
lengths[i+1, j+1] = max(lengths[i+1, j], lengths[i, j+1])
end
end
# read the substring out from the matrix
result = ""
x, y = length(a) + 1, length(b) + 1
while x > 1 && y > 1
if lengths[x, y] == lengths[x-1, y]
x -= 1
elseif lengths[x, y] == lengths[x, y-1]
y -= 1
else
@assert a[x-1] == b[y-1]
result = string(a[x-1], result)
x -= 1
y -= 1
end
end
return result
end
@show lcsrecursive("thisisatest", "testing123testing")
@time lcsrecursive("thisisatest", "testing123testing")
@show lcsdynamic("thisisatest", "testing123testing")
@time lcsdynamic("thisisatest", "testing123testing")</julia>
{{out}}
<pre>lcsrecursive("thisisatest", "testing123testing") = "tsitest"
0.038153 seconds (537.77 k allocations: 16.415 MiB)
lcsdynamic("thisisatest", "testing123testing") = "tsitest"
0.000004 seconds (12 allocations: 2.141 KiB)</pre>
=={{header|Kotlin}}==
| |||