Longest common subsequence: Difference between revisions
jq
(jq) |
|||
Line 1,157:
}</lang>
=={{header|jq}}==
We first give a recursive solution, and then use it to write a faster solution that removes extraneous characters and recognizes a common initial substring.<lang jq>
def recursive_lcs(a; b):
if (a|length) == 0 or (b|length) == 0 then ""
else a[0:-1] as $aSub
| b[0:-1] as $bSub
| a[-1:] as $last
| if $last == b[-1:] then recursive_lcs($aSub; $bSub) + $last
else recursive_lcs(a; $bSub) as $x
| recursive_lcs($aSub; b) as $y
| if ($x|length) > ($y|length) then $x else $y end
end
end ;</lang>
Enhanced version:<lang jq>
# return the length of the common initial subsequence;
# x and y are arrays
# The inner helper function has no arguments
# and so has no recursion overhead
def common_heads(x;y):
def common:
if x[.] != null and x[.] == y[.] then (.+1)|common else . end;
0 | common;
# x and y are arrays
def intersection(x;y):
( (x|unique) + (y|unique) | sort) as $sorted
| reduce range(1; $sorted|length) as $i
([]; if $sorted[$i] == $sorted[$i-1] then . + [$sorted[$i]] else . end) ;
# x and y are strings; emit [winnowedx, winnowedy]
def winnow(x; y):
(x|explode) as $x
| (y|explode) as $y
| intersection($x; $y) as $intersection
| [ ($x | map( select( . as $i | $intersection | index($i) ))) ,
($y | map( select( . as $i | $intersection | index($i) ))) ]
| map(implode) ;
# First remove extraneous characters and recognize common heads
def lcs(a; b):
if (a|length) == 0 or (b|length) == 0 then ""
else winnow(a;b)
| .[0] as $a | .[1] as $b
| common_heads($a | explode; $b | explode) as $heads
| if $heads > 0 then $a[0:$heads] + recursive_lcs( $a[$heads:]; b[$heads:])
else recursive_lcs($a; $b)
end
end ;</lang>
Example:<lang jq>
def test:
lcs( "thisisatest"; "testing123testing"),
lcs("beginning-middle-ending" ; "beginning-diddle-dum-ending" )
;
test</lang><lang sh>$ time jq -n -f LCS.jq
time jq -n -f LCS.jq
"tsitest"
"beginning-iddle-ending"
real 0m0.456s
user 0m0.427s
sys 0m0.005s</lang>
=={{header|Liberty BASIC}}==
<lang lb>
| |||