http://code.activestate.com/recipes/tags/bound/views/2013-10-02T12:52:23-07:00ActiveState Code Recipes2013-10-02T12:52:23-07:00Rutger Saalminkhttp://code.activestate.com/recipes/users/4187940/http://code.activestate.com/recipes/578678-shortest-common-supersequence-algorithms/

<p style="color: grey"> Python recipe 578678 by <a href="/recipes/users/4187940/">Rutger Saalmink</a> (<a href="/recipes/tags/approximation/">approximation</a>, <a href="/recipes/tags/bound/">bound</a>, <a href="/recipes/tags/breadth_first_search/">breadth_first_search</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/depth_first_search/">depth_first_search</a>, <a href="/recipes/tags/sequence/">sequence</a>, <a href="/recipes/tags/shortest/">shortest</a>, <a href="/recipes/tags/super/">super</a>). </p> <p>The Shortest Common Supersequence (SCS) problem is an NP-hard problem (<a href="https://en.wikipedia.org/wiki/Shortest_common_supersequence" rel="nofollow">https://en.wikipedia.org/wiki/Shortest_common_supersequence</a>), which occurs in problems originating from various domains, e.g. Bio Genetics. Given a set of strings, the common supersequence of minimal length is sought after. Below a set of algorithms is given, which I used in approximating and/or backtracking the optimal solution(s). </p>