Shortest common supersequence: Difference between revisions
→{{header|FreeBASIC}}: oops! I uploaded the code from another task. Corrected.
(Added Algol 68) |
(→{{header|FreeBASIC}}: oops! I uploaded the code from another task. Corrected.) |
||
(8 intermediate revisions by 6 users not shown) | |||
Line 18:
{{trans|C++}}
<
I x.empty
R y
Line 30:
R x[0]‘’scs(x[1..], y)
print(scs(‘abcbdab’, ‘bdcaba’))</
{{out}}
Line 39:
=={{header|Ada}}==
{{trans|C++}}
<
procedure Shortest is
Line 75:
Exercise ("abcbdab", "bdcaba");
Exercise ("WEASELS", "WARDANCE");
end Shortest;</
{{out}}
<pre>
Line 84:
=={{header|ALGOL 68}}==
{{Trans|C++}}
<
PRIO SCS = 1;
# returns the shortest common supersequence of x and y #
Line 102:
print( ( "abcbdab" SCS "bdcaba", newline ) )
END</
{{out}}
<pre>
Line 110:
=={{header|C}}==
The C99 code here isn't all that different from Levenstein distance calculation.
<
#include <string.h>
Line 163:
printf("SCS(%s, %s) -> %s\n", x, y, res);
return 0;
}</
{{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}}
<
std::string scs(std::string x, std::string y) {
Line 194 ⟶ 234:
std::cout << res << '\n';
return 0;
}</
{{out}}
<pre>abdcabdab</pre>
Line 200 ⟶ 240:
=={{header|D}}==
{{trans|Racket}}
<
dstring scs(in dstring x, in dstring y) nothrow @safe {
Line 216 ⟶ 256:
void main() @safe {
scs("abcbdab", "bdcaba").writeln;
}</
{{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}}==
Line 224 ⟶ 299:
{{works with|Elixir|1.3}}
uses 'LCS' from [[Longest common subsequence#Elixir|here]]
<
def scs(u, v) do
lcs = LCS.lcs(u, v) |> to_charlist
Line 238 ⟶ 313:
u = "abcbdab"
v = "bdcaba"
IO.puts "SCS(#{u}, #{v}) = #{SCS.scs(u, v)}"</
{{out}}
Line 247 ⟶ 322:
=={{header|Factor}}==
{{trans|Julia}}
<
MEMO:: scs ( x y -- seq )
Line 260 ⟶ 335:
} cond ;
"abcbdab" "bdcaba" scs print</
{{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}}
<
import (
Line 323 ⟶ 442:
v := "bdcaba"
fmt.Println(scs(u, v))
}</
{{out}}
Line 331 ⟶ 450:
=={{header|Haskell}}==
{{trans|C++}}
<
scs [] ys = ys
scs xs [] = xs
Line 343 ⟶ 462:
| otherwise = y : vs
main = putStrLn $ scs "abcbdab" "bdcaba"</
{{out}}
<pre>abdcabdab</pre>
=={{header|Java}}==
{{trans|D}}
<
private static boolean isEmpty(String s) {
return null == s || s.isEmpty();
Line 375 ⟶ 494:
System.out.println(scs("abcbdab", "bdcaba"));
}
}</
{{out}}
<pre>abdcabdab</pre>
Line 383 ⟶ 502:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<
# Uses recursion, taking advantage of jq's TCO
def lcs:
Line 419 ⟶ 538:
| .sb ;
[ "abcbdab", "bdcaba" ] | scs</
{{out}}
<pre>
Line 427 ⟶ 546:
=={{header|Julia}}==
{{trans|D}}
<
@memoize function scs(x, y)
Line 444 ⟶ 563:
println(scs("abcbdab", "bdcaba"))
</syntaxhighlight>
{{out}}
<pre>
Line 452 ⟶ 571:
=={{header|Kotlin}}==
Uses 'lcs' function from [[Longest common subsequence#Kotlin]]:
<
fun lcs(x: String, y: String): String {
Line 484 ⟶ 603:
val v = "bdcaba"
println(scs(u, v))
}</
{{out}}
Line 492 ⟶ 611:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
RosettaShortestCommonSuperSequence[aa_String, bb_String] :=
Module[{lcs, scs, a = aa, b = bb},
Line 516 ⟶ 635:
]
RosettaShortestCommonSuperSequence["abcbdab", "bdcaba"]
RosettaShortestCommonSuperSequence["WEASELS", "WARDANCE"]</
{{out}}
<pre>bdcabcbdaba
Line 523 ⟶ 642:
=={{header|Nim}}==
{{trans|Kotlin}}
<
if x.len == 0 or y.len == 0: return
let x1 = x[0..^2]
Line 551 ⟶ 670:
let u = "abcbdab"
let v = "bdcaba"
echo scs(u, v)</
{{out}}
Line 557 ⟶ 676:
=={{header|Perl}}==
<
my( $u, $v ) = @_;
return '' unless length($u) and length($v);
Line 588 ⟶ 707:
printf "Longest common subsequence: %s\n", lcs $u, $v;
printf "Shortest common supersquence: %s\n", scs $u, $v;
</syntaxhighlight>
{{out}}
<pre>Strings abcbdab bdcaba
Line 597 ⟶ 716:
=={{header|Phix}}==
{{trans|Python}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<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>
<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>
<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>
<span style="color: #008080;">else</span>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<span style="color: #000000;">scs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #000080;font-style:italic;">-- Consume lcs</span>
<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>
<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>
<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>
<span style="color: #000080;font-style:italic;">-- Part of the lcs, so consume from all strings</span>
<span style="color: #000000;">scs</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">c</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- append remaining characters</span>
<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>
<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 644 ⟶ 766:
=={{header|Python}}==
<syntaxhighlight lang="python">
# Use the Longest Common Subsequence algorithm
Line 666 ⟶ 788:
# append remaining characters
return scs + a + b
</syntaxhighlight>
{{out}}
<pre>
Line 676 ⟶ 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 .
<
(struct link (len letters))
Line 708 ⟶ 830:
(list->string (link-letters (scs/list (string->list x) (string->list y)))))
(scs "abcbdab" "bdcaba")</
{{out}}
<pre>"abdcabdab"</pre>
Line 716 ⟶ 838:
Using 'lcs' routine from [[Longest_common_subsequence#Raku|Longest common subsequence task]]
<syntaxhighlight lang="raku"
return "" unless $xstr && $ystr;
my ($x, $xs, $y, $ys) = $xstr.substr(0, 1), $xstr.substr(1), $ystr.substr(0, 1), $ystr.substr(1);
Line 739 ⟶ 861:
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;</
{{out}}
<pre>Strings: abcbdab bdcaba
Line 747 ⟶ 869:
=={{header|REXX}}==
{{trans|RING}}
<
parse arg u v . /*obtain optional arguments from the CL*/
if u=='' | u=="," then u= 'abcbdab' /*Not specified? Then use the default.*/
Line 762 ⟶ 884:
end /*n*/
say
say 'shortest common supersequence=' $ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 786 ⟶ 908:
=={{header|Ring}}==
<
# Project : Shortest common supersequence
Line 808 ⟶ 930:
next
see svect
</syntaxhighlight>
Output:
<pre>
Line 817 ⟶ 939:
{{trans|Tcl}}
uses 'lcs' from [[Longest common subsequence#Ruby|here]]
<
def scs(u, v)
Line 844 ⟶ 966:
u = "abcbdab"
v = "bdcaba"
puts "SCS(#{u}, #{v}) = #{scs(u, v)}"</
{{out}}
Line 854 ⟶ 976:
{{trans|Perl}}
Uses the ''lcs'' function defined [http://rosettacode.org/wiki/Longest_common_subsequence#Sidef here].
<
var ls = lcs(u, v).chars
var pat = Regex('(.*)'+ls.join('(.*)')+'(.*)')
Line 864 ⟶ 986:
}
say scs("abcbdab", "bdcaba")</
{{out}}
<pre>
Line 872 ⟶ 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>…
<
set lcs [lcs $u $v]
set scs ""
Line 902 ⟶ 1,024:
append scs [string range $u $ui end] [string range $v $vi end]
return $scs
}</
Demonstrating:
<
set v "bdcaba"
puts "SCS($u,$v) = [scs $u $v]"</
{{out}}
<pre>SCS(abcbdab,bdcaba) = abdcabdab</pre>
Line 912 ⟶ 1,034:
=={{header|Wren}}==
{{trans|Kotlin}}
<
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
Line 948 ⟶ 1,070:
var u = "abcbdab"
var v = "bdcaba"
System.print(scs.call(u, v))</
{{out}}
Line 957 ⟶ 1,079:
=={{header|zkl}}==
{{trans|C}}
<
fcn init(l=0,c="",lnk=Void){ len,letter,next=l,c,lnk; }
}
Line 984 ⟶ 1,106:
lp:=lnk[0][0]; while(lp){ out.write(lp.letter); lp=lp.next; }
out.close()
}</
<
{{out}}
<pre>
|