Rosetta Code

Shortest common supersequence: Difference between revisions

Page Discussion

Shortest common supersequence (view source)

Revision as of 19:42, 27 February 2024

20,396 bytes added ,  2 months ago
→‎{{header|FreeBASIC}}: oops! I uploaded the code from another task. Corrected.
(Add Factor)
(→‎{{header|FreeBASIC}}: oops! I uploaded the code from another task. Corrected.)
 
(21 intermediate revisions by 14 users not shown)
Line 12:
 
;Also see:
*   The Wikipedia article:   [http[wp://wikipedia.org/wiki/Shortest_common_supersequence_problem|Wikipedia: shortest common supersequence].]
<br><br>
 
=={{header|11l}}==
{{trans|C++}}
 
<syntaxhighlight lang="11l">F scs(String x, y)
I x.empty
R y
I y.empty
R x
I x[0] == y[0]
R x[0]‘’scs(x[1..], y[1..])
I scs(x, y[1..]).len <= scs(x[1..], y).len
R y[0]‘’scs(x, y[1..])
E
R x[0]‘’scs(x[1..], y)
 
print(scs(‘abcbdab’, ‘bdcaba’))</syntaxhighlight>
 
{{out}}
<pre>
abdcabdab
</pre>
 
=={{header|Ada}}==
{{trans|C++}}
<syntaxhighlight lang="ada">with Ada.Text_IO;
 
procedure Shortest is
 
function Scs (Left, Right : in String) return String is
Left_Tail : String renames Left (Left'First + 1 .. Left'Last);
Right_Tail : String renames Right (Right'First + 1 .. Right'Last);
begin
if Left = "" then return Right; end if;
if Right = "" then return Left; end if;
 
if Left (Left'First) = Right (Right'First) then
return Left (Left'First) & Scs (Left_Tail, Right_Tail);
end if;
 
declare
S1 : constant String := Scs (Left, Right_Tail);
S2 : constant String := Scs (Left_Tail, Right);
begin
return (if S1'Length <= S2'Length
then Right (Right'First) & S1
else Left (Left'First) & S2);
end;
end Scs;
 
procedure Exercise (Left, Right : String) is
use Ada.Text_Io;
begin
Put ("scs ( "); Put (Left); Put (" , "); Put (Right); Put ( " ) -> ");
Put (Scs (Left, Right));
New_Line;
end Exercise;
 
begin
Exercise ("abcbdab", "bdcaba");
Exercise ("WEASELS", "WARDANCE");
end Shortest;</syntaxhighlight>
{{out}}
<pre>
scs ( abcbdab , bdcaba ) -> abdcabdab
scs ( WEASELS , WARDANCE ) -> WARDEANCSELS
</pre>
 
=={{header|ALGOL 68}}==
{{Trans|C++}}
<syntaxhighlight lang="algol68">BEGIN
PRIO SCS = 1;
# returns the shortest common supersequence of x and y #
OP SCS = ( STRING x, y )STRING:
IF x = "" THEN y
ELIF y = "" THEN x
ELIF x[ LWB x ] = y[ LWB y ]
THEN x[ LWB x ] + ( x[ LWB x + 1 : ] SCS y[ LWB y + 1 : ] )
ELIF STRING x y sub = x SCS y[ LWB y + 1 : ];
STRING x sub y = x[ LWB x + 1 : ] SCS y;
INT x y sub size = ( UPB x y sub - LWB x y sub ) + 1;
INT x sub y size = ( UPB x sub y - LWB x sub y ) + 1;
x y sub size <= x sub y size
THEN y[ LWB y ] + x y sub
ELSE x[ LWB x ] + x sub y
FI # SCS # ;
print( ( "abcbdab" SCS "bdcaba", newline ) )
END</syntaxhighlight>
{{out}}
<pre>
abdcabdab
</pre>
 
=={{header|C}}==
The C99 code here isn't all that different from Levenstein distance calculation.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <string.h>
 
Line 70 ⟶ 163:
printf("SCS(%s, %s) -> %s\n", x, y, res);
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
SCS(abcbdab, bdcaba) -> abdcabdab
</pre>
 
=={{header|C sharp}}==
{{trans|Java}}This is based on the Java version, but with added caching.
<syntaxhighlight lang="csharp">public class ShortestCommonSupersequence
{
Dictionary<(string, string), string> cache = new();
 
public string scs(string x, string y)
{
if (x.Length == 0) return y;
if (y.Length == 0) return x;
 
if (cache.TryGetValue((x, y), out var result)) return result;
 
if (x[0] == y[0])
{
return cache[(x, y)] = x[0] + scs(x.Substring(1), y.Substring(1));
}
 
var xr = scs(x.Substring(1), y);
var yr = scs(x, y.Substring(1));
if (yr.Length <= xr.Length)
{
return cache[(x, y)] = y[0] + yr;
}
else
{
return cache[(x, y)] = x[0] + xr;
}
}
 
public static void Main(string[] args)
{
var scs = new ShortestCommonSupersequence();
Console.WriteLine(scs.scs("abcbdab", "bdcaba"));
}
}
</syntaxhighlight>
{{out}}
<pre>abdcabdab</pre>
 
=={{header|C++}}==
{{trans|Java}}
<syntaxhighlight lang="cpp">#include <iostream>
 
std::string scs(std::string x, std::string y) {
if (x.empty()) {
return y;
}
if (y.empty()) {
return x;
}
if (x[0] == y[0]) {
return x[0] + scs(x.substr(1), y.substr(1));
}
if (scs(x, y.substr(1)).size() <= scs(x.substr(1), y).size()) {
return y[0] + scs(x, y.substr(1));
} else {
return x[0] + scs(x.substr(1), y);
}
}
 
int main() {
auto res = scs("abcbdab", "bdcaba");
std::cout << res << '\n';
return 0;
}</syntaxhighlight>
{{out}}
<pre>abdcabdab</pre>
 
=={{header|D}}==
{{trans|Racket}}
<langsyntaxhighlight lang="d">import std.stdio, std.functional, std.array, std.range;
 
dstring scs(in dstring x, in dstring y) nothrow @safe {
Line 94 ⟶ 256:
void main() @safe {
scs("abcbdab", "bdcaba").writeln;
}</langsyntaxhighlight>
{{out}}
<pre>abdcabdab</pre>
 
=={{header|EasyLang}}==
{{trans|C++}}
<syntaxhighlight>
func$ car x$ .
return substr x$ 1 1
.
func$ cdr x$ .
return substr x$ 2 9999
.
func$ scs x$ y$ .
if x$ = ""
return y$
.
if y$ = ""
return x$
.
if car x$ = car y$
return car x$ & scs cdr x$ cdr y$
.
r1$ = scs x$ cdr y$
r2$ = scs cdr x$ y$
if len r1$ <= len r2$
return car y$ & r1$
else
return car x$ & r2$
.
.
print scs "abcbdab" "bdcaba"
</syntaxhighlight>
 
{{out}}
<pre>
abdcabdab
</pre>
 
=={{header|Elixir}}==
{{trans|Ruby}}
{{works with|Elixir|1.3}}
uses 'LCS' from [[Longest common subsequence#Elixir|here]]
<syntaxhighlight lang="elixir">defmodule SCS do
def scs(u, v) do
lcs = LCS.lcs(u, v) |> to_charlist
scs(to_charlist(u), to_charlist(v), lcs, []) |> to_string
end
defp scs(u, v, [], res), do: Enum.reverse(res) ++ u ++ v
defp scs([h|ut], [h|vt], [h|lt], res), do: scs(ut, vt, lt, [h|res])
defp scs([h|_]=u, [vh|vt], [h|_]=lcs, res), do: scs(u, vt, lcs, [vh|res])
defp scs([uh|ut], v, lcs, res), do: scs(ut, v, lcs, [uh|res])
end
 
u = "abcbdab"
v = "bdcaba"
IO.puts "SCS(#{u}, #{v}) = #{SCS.scs(u, v)}"</syntaxhighlight>
 
{{out}}
<pre>
SCS(abcbdab, bdcaba) = abdcabdab
</pre>
 
=={{header|Factor}}==
{{trans|Julia}}
<syntaxhighlight lang="factor">USING: combinators io kernel locals math memoize sequences ;
 
MEMO:: scs ( x y -- seq )
{
{ [ x empty? ] [ y ] }
{ [ y empty? ] [ x ] }
{ [ x first y first = ]
[ x rest y rest scs x first prefix ] }
{ [ x y rest scs length x rest y scs length <= ]
[ x y rest scs y first prefix ] }
[ x rest y scs x first prefix ]
} cond ;
 
"abcbdab" "bdcaba" scs print</syntaxhighlight>
{{out}}
<pre>
abdcabdab
</pre>
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vbnet">Function LCS(a As String, b As String) As String
Dim As String x, y
If Len(a) = 0 Or Len(b) = 0 Then
Return ""
Elseif Right(a, 1) = Right(b, 1) Then
LCS = LCS(Left(a, Len(a) - 1), Left(b, Len(b) - 1)) + Right(a, 1)
Else
x = LCS(a, Left(b, Len(b) - 1))
y = LCS(Left(a, Len(a) - 1), b)
If Len(x) > Len(y) Then Return x Else Return y
End If
End Function
 
Function SCS(u As String, v As String) As String
Dim lcsStr As String = LCS(u, v)
Dim As Integer i, ui = 0, vi = 0
Dim As String sb = ""
For i = 1 To Len(lcsStr)
While ui < Len(u) Andalso Mid(u, ui + 1, 1) <> Mid(lcsStr, i, 1)
sb += Mid(u, ui + 1, 1)
ui += 1
Wend
While vi < Len(v) Andalso Mid(v, vi + 1, 1) <> Mid(lcsStr, i, 1)
sb += Mid(v, vi + 1, 1)
vi += 1
Wend
sb += Mid(lcsStr, i, 1)
ui += 1
vi += 1
Next
If ui < Len(u) Then sb += Right(u, Len(u) - ui)
If vi < Len(v) Then sb += Right(v, Len(v) - vi)
Return sb
End Function
 
Print SCS("abcbdab", "bdcaba")
Print SCS("WEASELS", "WARDANCE")
 
Sleep</syntaxhighlight>
{{out}}
<pre>abdcabdab
WEASRDANCELS</pre>
 
=={{header|Go}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 155 ⟶ 442:
v := "bdcaba"
fmt.Println(scs(u, v))
}</langsyntaxhighlight>
 
{{out}}
Line 161 ⟶ 448:
abdcabdab
</pre>
=={{header|Haskell}}==
{{trans|C++}}
<syntaxhighlight lang="haskell">scs :: Eq a => [a] -> [a] -> [a]
scs [] ys = ys
scs xs [] = xs
scs xss@(x:xs) yss@(y:ys)
| x == y = x : scs xs ys
| otherwise = ws
where
us = scs xs yss
vs = scs xss ys
ws | length us < length vs = x : us
| otherwise = y : vs
 
main = putStrLn $ scs "abcbdab" "bdcaba"</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Rubyout}}
<pre>abdcabdab</pre>
{{works with|Elixir|1.3}}
=={{header|Java}}==
uses 'LCS' from [[Longest common subsequence#Elixir|here]]
{{trans|D}}
<lang elixir>defmodule SCS do
<syntaxhighlight lang="java">public class ShortestCommonSuperSequence {
def scs(u, v) do
private static boolean isEmpty(String s) {
lcs = LCS.lcs(u, v) |> to_charlist
return null == s || s.isEmpty();
scs(to_charlist(u), to_charlist(v), lcs, []) |> to_string
end }
defp scs(u, v, [], res), do: Enum.reverse(res) ++ u ++ v
defp scs([h|ut], [h|vt], [h|lt], res), do: scs(ut, vt, lt, [h|res])
defp scs([h|_]=u, [vh|vt], [h|_]=lcs, res), do: scs(u, vt, lcs, [vh|res])
defp scs([uh|ut], v, lcs, res), do: scs(ut, v, lcs, [uh|res])
end
 
private static String scs(String x, String y) {
u = "abcbdab"
if (isEmpty(x)) {
v = "bdcaba"
return y;
IO.puts "SCS(#{u}, #{v}) = #{SCS.scs(u, v)}"</lang>
}
if (isEmpty(y)) {
return x;
}
 
if (x.charAt(0) == y.charAt(0)) {
{{out}}
return x.charAt(0) + scs(x.substring(1), y.substring(1));
<pre>
}
SCS(abcbdab, bdcaba) = abdcabdab
</pre>
 
if (scs(x, y.substring(1)).length() <= scs(x.substring(1), y).length()) {
=={{header|Factor}}==
return y.charAt(0) + scs(x, y.substring(1));
{{trans|Julia}}
} else {
<lang factor>USING: combinators io kernel locals math memoize sequences ;
return x.charAt(0) + scs(x.substring(1), y);
}
}
 
public static void main(String[] args) {
MEMO:: scs ( x y -- seq )
System.out.println(scs("abcbdab", "bdcaba"));
{
}
{ [ x empty? ] [ y ] }
}</syntaxhighlight>
{ [ y empty? ] [ x ] }
{{out}}
{ [ x first y first = ]
<pre>abdcabdab</pre>
[ x rest y rest scs x first prefix ] }
{ [ x y rest scs length x rest y scs length <= ]
[ x y rest scs y first prefix ] }
[ x rest y scs x first prefix ]
} cond ;
 
=={{header|jq}}==
"abcbdab" "bdcaba" scs print</lang>
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight 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</syntaxhighlight>
{{out}}
<pre>
"abdcabdab"
</pre>
 
=={{header|Julia}}==
{{trans|D}}
<langsyntaxhighlight Julialang="julia">using Memoize
 
@memoize function scs(x, y)
Line 227 ⟶ 563:
 
println(scs("abcbdab", "bdcaba"))
</syntaxhighlight>
</lang>
{{out}}
<pre>
abdcabdab
</pre>
 
 
=={{header|Kotlin}}==
Uses 'lcs' function from [[Longest common subsequence#Kotlin]]:
<langsyntaxhighlight lang="scala">// version 1.1.2
 
fun lcs(x: String, y: String): String {
Line 268 ⟶ 603:
val v = "bdcaba"
println(scs(u, v))
}</langsyntaxhighlight>
 
{{out}}
Line 274 ⟶ 609:
abdcabdab
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[RosettaShortestCommonSuperSequence]
RosettaShortestCommonSuperSequence[aa_String, bb_String] :=
Module[{lcs, scs, a = aa, b = bb},
lcs = LongestCommonSubsequence[aa, bb];
scs = "";
While[StringLength[lcs] > 0,
If[StringTake[a, 1] == StringTake[lcs, 1] \[And] StringTake[b, 1] == StringTake[lcs, 1],
scs = StringJoin[scs, StringTake[lcs, 1]];
lcs = StringDrop[lcs, 1];
a = StringDrop[a, 1];
b = StringDrop[b, 1];
,
If[StringTake[a, 1] == StringTake[lcs, 1],
scs = StringJoin[scs, StringTake[b, 1]];
b = StringDrop[b, 1];
,
scs = StringJoin[scs, StringTake[a, 1]];
a = StringDrop[a, 1];
]
]
];
StringJoin[scs, a, b]
]
RosettaShortestCommonSuperSequence["abcbdab", "bdcaba"]
RosettaShortestCommonSuperSequence["WEASELS", "WARDANCE"]</syntaxhighlight>
{{out}}
<pre>bdcabcbdaba
WEASELSARDANCE</pre>
 
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">proc lcs(x, y: string): string =
if x.len == 0 or y.len == 0: return
let x1 = x[0..^2]
let y1 = y[0..^2]
if x[^1] == y[^1]: return lcs(x1, y1) & x[^1]
let x2 = lcs(x, y1)
let y2 = lcs(x1, y)
result = if x2.len > y2.len: x2 else: y2
 
proc scs(u, v: string): string =
let lcs = lcs(u, v)
var ui, vi = 0
for ch in lcs:
while ui < u.len and u[ui] != ch:
result.add u[ui]
inc ui
while vi < v.len and v[vi] != ch:
result.add v[vi]
inc vi
result.add ch
inc ui
inc vi
if ui < u.len: result.add u.substr(ui)
if vi < v.len: result.add v.substr(vi)
 
when isMainModule:
let u = "abcbdab"
let v = "bdcaba"
echo scs(u, v)</syntaxhighlight>
 
{{out}}
<pre>abdcabdab</pre>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">sub lcs { # longest common subsequence
my( $u, $v ) = @_;
return '' unless length($u) and length($v);
Line 307 ⟶ 707:
printf "Longest common subsequence: %s\n", lcs $u, $v;
printf "Shortest common supersquence: %s\n", scs $u, $v;
</syntaxhighlight>
</lang>
{{out}}
<pre>Strings abcbdab bdcaba
Line 313 ⟶ 713:
Shortest common supersquence: abdcabdab
</pre>
 
=={{header|Perl 6}}==
Using 'lcs' routine from [[Longest_common_subsequence#Perl_6 |Longest common subsequence task]]
<lang perl6>sub lcs(Str $xstr, Str $ystr) { # longest common subsequence
return "" unless $xstr && $ystr;
my ($x, $xs, $y, $ys) = $xstr.substr(0, 1), $xstr.substr(1), $ystr.substr(0, 1), $ystr.substr(1);
return $x eq $y
?? $x ~ lcs($xs, $ys)
!! max(:by{ $^a.chars }, lcs($xstr, $ys), lcs($xs, $ystr) );
}
 
sub scs ($u, $v) { # shortest common supersequence
my @lcs = (lcs $u, $v).comb;
my $pat = '(.*)' ~ join('(.*)',@lcs) ~ '(.*)';
my $regex = "rx/$pat/".EVAL;
my @u = ($u ~~ $regex).list;
my @v = ($v ~~ $regex).list;
my $scs = shift(@u) ~ shift(@v);
$scs ~= $_ ~ shift(@u) ~ shift(@v) for @lcs;
return $scs;
}
 
my $u = 'abcbdab';
my $v = 'bdcaba';
printf "Strings: %s %s\n", $u, $v;
printf "Longest common subsequence: %s\n", lcs $u, $v;
printf "Shortest common supersquence: %s\n", scs $u, $v;</lang>
{{out}}
<pre>Strings: abcbdab bdcaba
Longest common subsequence: bcba
Shortest common supersquence: abdcabdab</pre>
 
=={{header|Phix}}==
{{trans|Python}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>function longest_common_subsequence(sequence a, b)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence res = ""
<span style="color: #008080;">function</span> <span style="color: #000000;">longest_common_subsequence</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
if length(a) and length(b) then
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
if a[$]=b[$] then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
res = longest_common_subsequence(a[1..-2],b[1..-2])&a[$]
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[$]=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">longest_common_subsequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[$]</span>
sequence l = longest_common_subsequence(a,b[1..-2]),
<span style="color: #008080;">else</span>
r = longest_common_subsequence(a[1..-2],b)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">longest_common_subsequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]),</span>
res = iff(length(l)>length(r)?l:r)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">longest_common_subsequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">l</span><span style="color: #0000FF;">:</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function shortest_common_supersequence(string a, b)
string lcs = longest_common_subsequence(a, b),
<span style="color: #008080;">function</span> <span style="color: #000000;">shortest_common_supersequence</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
scs = ""
<span style="color: #004080;">string</span> <span style="color: #000000;">lcs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">longest_common_subsequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">),</span>
-- Consume lcs
<span style="color: #000000;">scs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
while length(lcs) do
<span style="color: #000080;font-style:italic;">-- Consume lcs</span>
integer c = lcs[1]
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lcs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if a[1]==c and b[1]==c then
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lcs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
-- Part of the lcs, so consume from all strings
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">and</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
scs &= c
<span style="color: #000080;font-style:italic;">-- Part of the lcs, so consume from all strings</span>
lcs = lcs[2..$]
<span style="color: #000000;">scs</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">c</span>
a = a[2..$]
<span style="color: #000000;">lcs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lcs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
b = b[2..$]
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
elsif a[1]==c then
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
scs &= b[1]
<span style="color: #008080;">elsif</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
b = b[2..$]
<span style="color: #000000;">scs</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
else
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
scs &= a[1]
<span a style="color: a[2..$]#008080;">else</span>
<span style="color: #000000;">scs</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- append remaining characters
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return scs & a & b
<span style="color: #000080;font-style:italic;">-- append remaining characters</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">scs</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">b</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
?shortest_common_supersequence("abcbdab", "bdcaba")
?shortest_common_supersequence("WEASELS", "WARDANCE")</lang>
<span style="color: #0000FF;">?</span><span style="color: #000000;">shortest_common_supersequence</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"abcbdab"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"bdcaba"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">shortest_common_supersequence</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"WEASELS"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"WARDANCE"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 394 ⟶ 766:
 
=={{header|Python}}==
<syntaxhighlight lang="python">
<lang Python>
# Use the Longest Common Subsequence algorithm
 
Line 416 ⟶ 788:
# append remaining characters
return scs + a + b
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 426 ⟶ 798:
=={{header|Racket}}==
{{trans|C}}This program is based on the C implementation, but use memorization instead of dynamic programming. More explanations about the memorization part in http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html .
<langsyntaxhighlight Racketlang="racket">#lang racket
 
(struct link (len letters))
Line 458 ⟶ 830:
(list->string (link-letters (scs/list (string->list x) (string->list y)))))
 
(scs "abcbdab" "bdcaba")</langsyntaxhighlight>
{{out}}
<pre>"abdcabdab"</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
 
Using 'lcs' routine from [[Longest_common_subsequence#Raku|Longest common subsequence task]]
<syntaxhighlight lang="raku" line>sub lcs(Str $xstr, Str $ystr) { # longest common subsequence
return "" unless $xstr && $ystr;
my ($x, $xs, $y, $ys) = $xstr.substr(0, 1), $xstr.substr(1), $ystr.substr(0, 1), $ystr.substr(1);
return $x eq $y
?? $x ~ lcs($xs, $ys)
!! max(:by{ $^a.chars }, lcs($xstr, $ys), lcs($xs, $ystr) );
}
 
sub scs ($u, $v) { # shortest common supersequence
my @lcs = (lcs $u, $v).comb;
my $pat = '(.*)' ~ join('(.*)',@lcs) ~ '(.*)';
my $regex = "rx/$pat/".EVAL;
my @u = ($u ~~ $regex).list;
my @v = ($v ~~ $regex).list;
my $scs = shift(@u) ~ shift(@v);
$scs ~= $_ ~ shift(@u) ~ shift(@v) for @lcs;
return $scs;
}
 
my $u = 'abcbdab';
my $v = 'bdcaba';
printf "Strings: %s %s\n", $u, $v;
printf "Longest common subsequence: %s\n", lcs $u, $v;
printf "Shortest common supersquence: %s\n", scs $u, $v;</syntaxhighlight>
{{out}}
<pre>Strings: abcbdab bdcaba
Longest common subsequence: bcba
Shortest common supersquence: abdcabdab</pre>
 
=={{header|REXX}}==
{{trans|RING}}
<langsyntaxhighlight lang="rexx">/*REXX program finds the Shortest common supersequence (SCS) of two character strings.*/
parse arg u v . /*obtain optional arguments from the CL*/
if u=='' | u=="," then u= 'abcbdab' /*Not specified? Then use the default.*/
Line 479 ⟶ 884:
end /*n*/
say
say 'shortest common supersequence=' $ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 503 ⟶ 908:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Shortest common supersequence
 
Line 525 ⟶ 930:
next
see svect
</syntaxhighlight>
</lang>
Output:
<pre>
Line 534 ⟶ 939:
{{trans|Tcl}}
uses 'lcs' from [[Longest common subsequence#Ruby|here]]
<langsyntaxhighlight lang="ruby">require 'lcs'
 
def scs(u, v)
Line 561 ⟶ 966:
u = "abcbdab"
v = "bdcaba"
puts "SCS(#{u}, #{v}) = #{scs(u, v)}"</langsyntaxhighlight>
 
{{out}}
Line 571 ⟶ 976:
{{trans|Perl}}
Uses the ''lcs'' function defined [http://rosettacode.org/wiki/Longest_common_subsequence#Sidef here].
<langsyntaxhighlight lang="ruby">func scs(u, v) {
var ls = lcs(u, v).chars
var pat = Regex('(.*)'+ls.join('(.*)')+'(.*)')
Line 581 ⟶ 986:
}
 
say scs("abcbdab", "bdcaba")</langsyntaxhighlight>
{{out}}
<pre>
Line 589 ⟶ 994:
=={{header|Tcl}}==
This example uses either of the <code>lcs</code> implementations from [[longest common subsequence#Tcl|here]], assumed renamed to <tt>lcs</tt>…
<langsyntaxhighlight lang="tcl">proc scs {u v} {
set lcs [lcs $u $v]
set scs ""
Line 619 ⟶ 1,024:
append scs [string range $u $ui end] [string range $v $vi end]
return $scs
}</langsyntaxhighlight>
Demonstrating:
<langsyntaxhighlight lang="tcl">set u "abcbdab"
set v "bdcaba"
puts "SCS($u,$v) = [scs $u $v]"</langsyntaxhighlight>
{{out}}
<pre>SCS(abcbdab,bdcaba) = abdcabdab</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">var lcs // recursive
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
var x1 = x[0...-1]
var y1 = y[0...-1]
if (x[-1] == y[-1]) return lcs.call(x1, y1) + x[-1]
var x2 = lcs.call(x, y1)
var y2 = lcs.call(x1, y)
return (x2.count > y2.count) ? x2 : y2
}
 
var scs = Fn.new { |u, v|
var lcs = lcs.call(u, v)
var ui = 0
var vi = 0
var sb = ""
for (i in 0...lcs.count) {
while (ui < u.count && u[ui] != lcs[i]) {
sb = sb + u[ui]
ui = ui + 1
}
while (vi < v.count && v[vi] != lcs[i]) {
sb = sb + v[vi]
vi = vi + 1
}
sb = sb + lcs[i]
ui = ui + 1
vi = vi + 1
}
if (ui < u.count) sb = sb + u[ui..-1]
if (vi < v.count) sb = sb + v[vi..-1]
return sb
}
 
var u = "abcbdab"
var v = "bdcaba"
System.print(scs.call(u, v))</syntaxhighlight>
 
{{out}}
<pre>
abdcabdab
</pre>
 
=={{header|zkl}}==
{{trans|C}}
<langsyntaxhighlight lang="zkl">class Link{ var len,letter,next;
fcn init(l=0,c="",lnk=Void){ len,letter,next=l,c,lnk; }
}
Line 656 ⟶ 1,106:
lp:=lnk[0][0]; while(lp){ out.write(lp.letter); lp=lp.next; }
out.close()
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">scs("abcbdab","bdcaba", Sink(String)).println();</langsyntaxhighlight>
{{out}}
<pre>
Jjuanhdez
2,122

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/226939...360949"