Shortest common supersequence: Difference between revisions
Content added Content deleted
m (minor rewording: find it) |
m (omissions) |
||
| Line 5: | Line 5: | ||
As an example, for the strings 'AACCTTGG' and 'ACACTGTGA' and you should get 'AACTGG'. Sometimes several solutions are possible, though they should all have the same length by definition. This example is taken from a [http://rosalind.info/problems/lcsq/ rosalind task]. |
As an example, for the strings 'AACCTTGG' and 'ACACTGTGA' and you should get 'AACTGG'. Sometimes several solutions are possible, though they should all have the same length by definition. This example is taken from a [http://rosalind.info/problems/lcsq/ rosalind task]. |
||
{{omit from|Brlcad}} |
|||
{{omit from|GUISS}} |
|||
{{omit from|Lilypond}} |
|||
{{omit from|Openscad}} |
|||
{{omit from|TPP}} |
|||
Revision as of 07:08, 31 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, find the shortest possible sequence s, which is the shortest common supersequence of u and v where both u and v are a subsequence of s.
As an example, for the strings 'AACCTTGG' and 'ACACTGTGA' and you should get 'AACTGG'. Sometimes several solutions are possible, though they should all have the same length by definition. This example is taken from a rosalind task.