Anonymous user
Shortest common supersequence: Difference between revisions
→{{header|C sharp}}: New language: C#
(Added Algol 68) |
(→{{header|C sharp}}: New language: C#) |
||
Line 168:
SCS(abcbdab, bdcaba) -> abdcabdab
</pre>
=={{header|C sharp}}==
{{trans|Java}}This is based on the Java version, but with added caching.
<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"));
}
}
</lang>
{{out}}
<pre>abdcabdab</pre>
=={{header|C++}}==
|