Shortest common supersequence: Difference between revisions

=={{header|D}}==

{{trans|Scheme}}

<lang d>import std.stdio, std.functional, std.array, std.range;

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

alias mScs = memoize!scs;

if (x.empty) return y;

if (y.empty) return x;

if (x.front == y.front)

return x.front ~ mScs(x.dropOne, y.dropOne);

if (mScs(x, y.dropOne).length <= mScs(x.dropOne, y).length)

return y.front ~ mScs(x, y.dropOne);

else

return x.front ~ mScs(x.dropOne, y);

}

void main() {

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

}</lang>

{{out}}

<pre>abdcabdab</pre>