Shortest common supersequence: Difference between revisions
Content deleted Content added
mention of non-uniqueness of the solution |
|||
Line 2: | Line 2: | ||
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. |
||
Given two strings <math>u</math> and <math>v</math>, find the shortest possible sequence <math>s</math>, which is the shortest common supersequence of <math>u</math> and <math>v</math> where both <math>u</math> and <math>v</math> are a subsequence of <math>s</math>. |
Given two strings <math>u</math> and <math>v</math>, find the shortest possible sequence <math>s</math>, which is the shortest common supersequence 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. |
||
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 <math>s</math> where <math>u = </math>“<tt>abcbdab</tt>” and <math>v = </math>“<tt>bdcaba</tt>”. |