Shortest common supersequence: Difference between revisions
Content deleted Content added
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}} |