Shortest common supersequence: Difference between revisions
Content added Content deleted
Line 307: | Line 307: | ||
{{out}} |
{{out}} |
||
<pre>abdcabdab</pre> |
<pre>abdcabdab</pre> |
||
=={{header|jq}}== |
|||
{{trans|Wren}} |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<lang jq># largest common substring |
|||
# Uses recursion, taking advantage of jq's TCO |
|||
def lcs: |
|||
. as [$x, $y] |
|||
| if ($x|length == 0) or ($y|length == 0) then "" |
|||
else $x[:-1] as $x1 |
|||
| $y[:-1] as $y1 |
|||
| if $x[-1:] == $y[-1:] then ([$x1, $y1] | lcs) + $x[-1:] |
|||
else ([$x, $y1] | lcs) as $x2 |
|||
| ([$x1, $y] | lcs) as $y2 |
|||
| if ($x2|length) > ($y2|length) then $x2 else $y2 end |
|||
end |
|||
end; |
|||
def scs: |
|||
def eq($s;$i; $t;$j): $s[$i:$i+1] == $t[$j:$j+1]; |
|||
. as [$u, $v] |
|||
| lcs as $lcs |
|||
| reduce range(0; $lcs|length) as $i ( { ui: 0, vi: 0, sb: "" }; |
|||
until( .ui == ($u|length) or eq($u;.ui; $lcs;$i); |
|||
.ui as $ui |
|||
| .sb += $u[$ui:$ui+1] |
|||
| .ui += 1 ) |
|||
| until(.vi == ($v|length) or eq($v;.vi; $lcs;$i); |
|||
.vi as $vi |
|||
| .sb += $v[$vi:$vi+1] |
|||
| .vi += 1 ) |
|||
| .sb += $lcs[$i:$i+1] |
|||
| .ui += 1 |
|||
| .vi += 1 |
|||
) |
|||
| if .ui < ($u|length) then .sb = .sb + $u[.ui:] else . end |
|||
| if .vi < ($v|length) then .sb = .sb + $v[.vi:] else . end |
|||
| .sb ; |
|||
[ "abcbdab", "bdcaba" ] | scs</lang> |
|||
{{out}} |
|||
<pre> |
|||
"abdcabdab" |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |