Shortest common supersequence: Difference between revisions
Content added Content deleted
m (moved Shortest common superstring to Shortest common supersequence: incorrect vocabulary) |
(use of the longest common subsequence as an external function is allowed) |
||
| Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
The '''[[wp:shortest common supersequence|shortest common supersequence]]''' is a problem closely related to the [[longest common subsequence]]. |
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 u and v, the shortest common supersequence of u and v is the shortest possible sequence s such that both u and v are a subsequence of s. |
Given two strings u and v, the shortest common supersequence of u and v is the shortest possible sequence s such that both u and v are a subsequence of s. |
||
Revision as of 19:29, 2 March 2013
Shortest common supersequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The 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 u and v, the shortest common supersequence of u and v is the shortest possible sequence s such that both u and v are a subsequence of s.
As an example, you'll take the strings 'AACCTTGG' and 'ACACTGTGA' and you should get 'AACTGG' for instance (sometimes several solutions are possible, though they should all have the same length by definition). This example is taken from a rosalind task.