Anonymous user
Shortest common supersequence: Difference between revisions
→Tcl: Added implementation
(this is wrong) |
(→Tcl: Added implementation) |
||
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.
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}}
| |||