Rosetta Code

Shortest common supersequence: Difference between revisions

Page Discussion

Shortest common supersequence (view source)

Revision as of 02:49, 26 August 2016

478 bytes added ,  7 years ago
m
added whitespace and highlighting to the task's preamble.
m (added whitespace before the TOC (table of contents), added a ;Task: (bold) header.)
m (added whitespace and highlighting to the task's preamble.)
Line 1:
{{draft task}}
 
The   '''[[wp:shortest common supersequence|shortest common supersequence]]'''   is a problem closely related to the   [[longest common subsequence]],   which you can use as an external function for this task.
 
 
;Task:
Given two strings &nbsp; <big><big><math> u </math></big></big> &nbsp; and &nbsp; <big><big><math> v, </math>,</big></big> &nbsp; find the shortest possible sequence &nbsp; <big><big><math> s, </math>,</big></big> &nbsp; which is the shortest common super-sequence of &nbsp; <big><big><math> u </math></big></big> &nbsp; and &nbsp; <big><big><math> v </math></big></big> &nbsp; where both &nbsp; <big><big><math> u </math></big></big> &nbsp; and &nbsp; <big><big><math> v </math></big></big> &nbsp; are a subsequence of &nbsp; <big><big><math> s.</math>.</big></big> &nbsp; Defined as such, &nbsp; <big><big><math> s </math></big></big> &nbsp; is not necessarily unique.
 
 
Demonstrate this by printing <math>s</math> where <math>u = </math>“<tt>abcbdab</tt>” and <math>v = </math>“<tt>bdcaba</tt>”.
Demonstrate this by printing &nbsp; <big><big><math>s</math></big></big> &nbsp; where
<big><big><math> u = </math><big><code>abcbdab</code></big></big></big>
and
<big><big><math> v = </math><big><code>bdcaba</code></big></big></big>
<!-- This example is taken from the Wikipedia page. -->
<br><br>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/226922"