Shortest common supersequence: Difference between revisions
Content added Content deleted
(Added Algol 68) |
(→{{header|C sharp}}: New language: C#) |
||
Line 168: | Line 168: | ||
SCS(abcbdab, bdcaba) -> abdcabdab |
SCS(abcbdab, bdcaba) -> abdcabdab |
||
</pre> |
</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++}}== |
=={{header|C++}}== |