Shortest common supersequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(Created page with "{{draft task}} The '''shortest common superstring''' is a problem closely related to the longest common subsequence. Given two strings u and v, the shortest common supers...")
 
(wikipedia and rosalind links)
Line 1: Line 1:
{{draft task}}
{{draft task}}
The '''shortest common superstring''' is a problem closely related to the [[longest common subsequence]].
The '''[[wp:shortest common superstring|shortest common superstring]]''' is a problem closely related to the [[longest common subsequence]].


Given two strings u and v, the shortest common superstring of u and v is the shortest possible string s such that both u and v are a subsequence of s.
Given two strings u and v, the shortest common superstring of u and v is the shortest possible string 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).
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 [http://rosalind.info/problems/lcsq/ rosalind task].

Revision as of 18:54, 22 February 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 superstring is a problem closely related to the longest common subsequence.

Given two strings u and v, the shortest common superstring of u and v is the shortest possible string 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.