Shortest common supersequence: Difference between revisions

{{trans|C++}}

 

I x.empty

R y

R x[0]‘’scs(x[1..], y)

 

 

{{out}}

=={{header|Ada}}==

{{trans|C++}}

 

procedure Shortest is

Exercise ("abcbdab", "bdcaba");

Exercise ("WEASELS", "WARDANCE");

{{out}}

<pre>

=={{header|ALGOL 68}}==

{{Trans|C++}}

PRIO SCS = 1;

# returns the shortest common supersequence of x and y #

print( ( "abcbdab" SCS "bdcaba", newline ) )

{{out}}

<pre>

=={{header|C}}==

The C99 code here isn't all that different from Levenstein distance calculation.

#include <string.h>

 

printf("SCS(%s, %s) -> %s\n", x, y, res);

return 0;

{{out}}

<pre>

=={{header|C sharp}}==

{{trans|Java}}This is based on the Java version, but with added caching.

{

Dictionary<(string, string), string> cache = new();

}

}

{{out}}

<pre>abdcabdab</pre>

=={{header|C++}}==

{{trans|Java}}

 

std::string scs(std::string x, std::string y) {

std::cout << res << '\n';

return 0;

{{out}}

<pre>abdcabdab</pre>

=={{header|D}}==

{{trans|Racket}}

 

dstring scs(in dstring x, in dstring y) nothrow @safe {

void main() @safe {

scs("abcbdab", "bdcaba").writeln;

{{out}}

<pre>abdcabdab</pre>

{{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

u = "abcbdab"

v = "bdcaba"

 

{{out}}

=={{header|Factor}}==

{{trans|Julia}}

 

MEMO:: scs ( x y -- seq )

} cond ;

 

{{out}}

<pre>

=={{header|Go}}==

{{trans|Kotlin}}

 

import (

v := "bdcaba"

fmt.Println(scs(u, v))

 

{{out}}

=={{header|Haskell}}==

{{trans|C++}}

scs [] ys = ys

scs xs [] = xs

| otherwise = y : vs

 

{{out}}

<pre>abdcabdab</pre>

=={{header|Java}}==

{{trans|D}}

private static boolean isEmpty(String s) {

return null == s || s.isEmpty();

System.out.println(scs("abcbdab", "bdcaba"));

}

{{out}}

<pre>abdcabdab</pre>

{{works with|jq}}

'''Works with gojq, the Go implementation of jq'''

# Uses recursion, taking advantage of jq's TCO

def lcs:

| .sb ;

{{out}}

<pre>

=={{header|Julia}}==

{{trans|D}}

 

@memoize function scs(x, y)

 

println(scs("abcbdab", "bdcaba"))

{{out}}

<pre>

=={{header|Kotlin}}==

Uses 'lcs' function from [[Longest common subsequence#Kotlin]]:

 

fun lcs(x: String, y: String): String {

val v = "bdcaba"

println(scs(u, v))

 

{{out}}

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

RosettaShortestCommonSuperSequence[aa_String, bb_String] :=

Module[{lcs, scs, a = aa, b = bb},

]

RosettaShortestCommonSuperSequence["abcbdab", "bdcaba"]

{{out}}

<pre>bdcabcbdaba

=={{header|Nim}}==

{{trans|Kotlin}}

if x.len == 0 or y.len == 0: return

let x1 = x[0..^2]

let u = "abcbdab"

let v = "bdcaba"

 

{{out}}

 

=={{header|Perl}}==

my( $u, $v ) = @_;

return '' unless length($u) and length($v);

printf "Longest common subsequence: %s\n", lcs $u, $v;

printf "Shortest common supersquence: %s\n", scs $u, $v;

{{out}}

<pre>Strings abcbdab bdcaba

=={{header|Phix}}==

{{trans|Python}}

<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: #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>

{{out}}

<pre>

 

=={{header|Python}}==

# Use the Longest Common Subsequence algorithm

 

# append remaining characters

return scs + a + b

{{out}}

<pre>

=={{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))

(list->string (link-letters (scs/list (string->list x) (string->list y)))))

 

{{out}}

<pre>"abdcabdab"</pre>

 

Using 'lcs' routine from [[Longest_common_subsequence#Raku|Longest common subsequence task]]

return "" unless $xstr && $ystr;

my ($x, $xs, $y, $ys) = $xstr.substr(0, 1), $xstr.substr(1), $ystr.substr(0, 1), $ystr.substr(1);

printf "Strings: %s %s\n", $u, $v;

printf "Longest common subsequence: %s\n", lcs $u, $v;

{{out}}

<pre>Strings: abcbdab bdcaba

=={{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.*/

end /*n*/

say

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Shortest common supersequence

 

next

see svect

Output:

<pre>

{{trans|Tcl}}

uses 'lcs' from [[Longest common subsequence#Ruby|here]]

 

def scs(u, v)

u = "abcbdab"

v = "bdcaba"

 

{{out}}

{{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('(.*)')+'(.*)')

}

 

{{out}}

<pre>

=={{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 ""

append scs [string range $u $ui end] [string range $v $vi end]

return $scs

Demonstrating:

set v "bdcaba"

{{out}}

<pre>SCS(abcbdab,bdcaba) = abdcabdab</pre>

=={{header|Wren}}==

{{trans|Kotlin}}

lcs = Fn.new { |x, y|

if (x.count == 0 || y.count == 0) return ""

var u = "abcbdab"

var v = "bdcaba"

 

{{out}}

=={{header|zkl}}==

{{trans|C}}

fcn init(l=0,c="",lnk=Void){ len,letter,next=l,c,lnk; }

}

lp:=lnk[0][0]; while(lp){ out.write(lp.letter); lp=lp.next; }

out.close()

{{out}}

<pre>