15 lines
871 B
Plaintext
15 lines
871 B
Plaintext
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.
|
|
|
|
Demonstrate this by printing <math>s</math> where <math>u = </math>“<tt>abcbdab</tt>” and <math>v = </math>“<tt>bdcaba</tt>”.
|
|
<!-- This example is taken from the Wikipedia page. -->
|
|
|
|
|
|
;Also see:
|
|
* [[wp:Shortest_common_supersequence_problem|Wikipedia: shortest common supersequence]]
|
|
<br><br>
|
|
|