Shortest common supersequence: Difference between revisions
this is wrong |
→Tcl: Added implementation |
||
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 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. |
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>. |
||
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. --> |
|||
=={{header|Tcl}}== |
|||
This example uses either of the <code>lcs</code> implementations from [[longest common subsequence#Tcl|here]], assumed renamed to <tt>lcs</tt>… |
|||
<lang tcl>proc scs {u v} { |
|||
set lcs [lcs $u $v] |
|||
set scs "" |
|||
# Iterate over the characters until LCS processed |
|||
for {set ui [set vi [set li 0]]} {$li<[string length $lcs]} {} { |
|||
set uc [string index $u $ui] |
|||
set vc [string index $v $vi] |
|||
set lc [string index $lcs $li] |
|||
if {$uc eq $lc} { |
|||
if {$vc eq $lc} { |
|||
# Part of the LCS, so consume from all strings |
|||
append scs $lc |
|||
incr ui |
|||
incr li |
|||
} else { |
|||
# char of u = char of LCS, but char of LCS v doesn't so consume just that |
|||
append scs $vc |
|||
} |
|||
incr vi |
|||
} else { |
|||
# char of u != char of LCS, so consume just that |
|||
append scs $uc |
|||
incr ui |
|||
} |
|||
} |
|||
# append remaining characters, which are not in common |
|||
append scs [string range $u $ui end] [string range $v $vi end] |
|||
return $scs |
|||
}</lang> |
|||
Demonstrating: |
|||
<lang tcl>set u "abcbdab" |
|||
set v "bdcaba" |
|||
puts "SCS($u,$v) = [scs $u $v]"</lang> |
|||
{{out}} |
|||
<pre>SCS(abcbdab,bdcaba) = abdcabdab</pre> |
|||
{{omit from|Brlcad}} |
{{omit from|Brlcad}} |
Revision as of 16:43, 25 May 2013
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 and , find the shortest possible sequence , which is the shortest common supersequence of and where both and are a subsequence of .
Demonstrate this by printing where “abcbdab” and “bdcaba”.
Tcl
This example uses either of the lcs
implementations from here, assumed renamed to lcs…
<lang tcl>proc scs {u v} {
set lcs [lcs $u $v] set scs ""
# Iterate over the characters until LCS processed for {set ui [set vi [set li 0]]} {$li<[string length $lcs]} {} {
set uc [string index $u $ui] set vc [string index $v $vi] set lc [string index $lcs $li] if {$uc eq $lc} { if {$vc eq $lc} { # Part of the LCS, so consume from all strings append scs $lc incr ui incr li } else { # char of u = char of LCS, but char of LCS v doesn't so consume just that append scs $vc } incr vi } else { # char of u != char of LCS, so consume just that append scs $uc incr ui }
}
# append remaining characters, which are not in common append scs [string range $u $ui end] [string range $v $vi end] return $scs
}</lang> Demonstrating: <lang tcl>set u "abcbdab" set v "bdcaba" puts "SCS($u,$v) = [scs $u $v]"</lang>
- Output:
SCS(abcbdab,bdcaba) = abdcabdab