Shortest common supersequence: Difference between revisions

Line 1:

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.

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 <math>u</math> and <math>v</math>, find the shortest possible sequence <math>s</math>, which is the shortest common super-sequence of <math>u</math> and <math>v</math> where both <math>u</math> and <math>v</math> are a subsequence of <math>s</math>. Defined as such, <math>s</math> is not necessarily unique.

Given two strings   <big><big><math> u </math></big></big>   and   <big><big><math> v, </math></big></big>   find the shortest possible sequence   <big><big><math> s, </math></big></big>   which is the shortest common super-sequence of   <big><big><math> u </math></big></big>   and   <big><big><math> v </math></big></big>   where both   <big><big><math> u </math></big></big>   and   <big><big><math> v </math></big></big>   are a subsequence of   <big><big><math> s.</math></big></big>   Defined as such,   <big><big><math> s </math></big></big>   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   <big><big><math>s</math></big></big>   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>