Shortest common supersequence: Difference between revisions

Content added Content deleted

Inline

@@ Line 197: / Line 197: @@
 Longest common subsequence:   bcba
 Shortest common supersquence: abdcabdab
+</pre>
+=={{header|Python}}==
+<lang Python>
+# Use the Longest Common Subsequence algorithm
+def shortest_common_supersequence(a, b):
+    lcs = longest_common_subsequence(a, b)
+    scs = ""
+    # Consume lcs
+    while len(lcs) > 0:
+        if a[0]==lcs[0] and b[0]==lcs[0]:
+        # Part of the LCS, so consume from all strings
+            scs += lcs[0]
+            lcs = lcs[1:]
+            a = a[1:]
+            b = b[1:]
+        elif a[0]==lcs[0]:
+            scs += b[0]
+            b = b[1:]
+        else:
+            scs += a[0]
+            a = a[1:]
+    # append remaining characters
+    return scs + a + b
+</lang>
+{{out}}
+<pre>
+Seq1: WEASELS
+Seq2: WARDANCE
+SCS:  WEASRDANCELS
 </pre>