Unique Subsequence

You are given two strings $S and $T. Write a script to find out count of different unique subsequences matching $T without changing the position of characters.

這題可以用遞迴來理解，下面就是基本條件：

• Given the string T is an empty string, returning 1 as an empty string can be the subsequence of all.
• Given the string S is an empty string, returning 0 as no string can be the subsequence of an empty string.

#!/usr/bin/env tclsh
#
# You are given two strings $S and $T.
# Write a script to find out count of different unique 
# subsequences matching $T without changing the position 
# of characters.
#
proc findSubsequenceCount {str1 str2 n m} {
    array set mat {}

    if {$m > $n} {
        return 0
    }

    if {$m == 0} {
        return 1
    }

    if {$n == 0} {
        return 0
    }

    set nvalue [tcl::mathop::- $n 1]
    set mvalue [tcl::mathop::- $m 1]

    if {[string index $str1 $nvalue] != [string index $str2 $mvalue]} {
        return [findSubsequenceCount $str1 $str2 $nvalue $m]
    } else {
        return [tcl::mathop::+ [findSubsequenceCount $str1 $str2 $nvalue $m] \
               [findSubsequenceCount $str1 $str2 $nvalue $mvalue]]
    }
}

if {$argc != 2} {
    exit
}

set s1 [lindex $argv 0]
set s2 [lindex $argv 1]
set n [string length $s1]
set m [string length $s2]

set r [findSubsequenceCount $s1 $s2 $n $m]
puts "Output: $r"

使用動態規畫的解法：

#!/usr/bin/env tclsh
#
# You are given two strings $S and $T.
# Write a script to find out count of different unique 
# subsequences matching $T without changing the position 
# of characters.
#
proc findSubsequenceCount {str1 str2} {
    array set mat {}

    set n [string length $str1]
    set m [string length $str2]

    if {$n == 0 && $m == 0} {
        return 1
    }

    if {$m > $n} {
        return 0
    }

    # An empty string can't have another string as suhsequence 
    for {set i 1} {$i <= $m} {incr i} {
        set mat($i,0) 0
    }

    # An empty string is subsequence of all
    for {set j 0} {$j <= $n} {incr j} {
        set mat(0,$j) 1
    }

    for {set i 1} {$i <= $m} {incr i} {
        for {set j 1} {$j <= $n} {incr j} {
            set ivalue [tcl::mathop::- $i 1]
            set jvalue [tcl::mathop::- $j 1]

            if {[string index $str2 $ivalue] != [string index $str1 $jvalue]} {
                set mat($i,$j) $mat($i,$jvalue)
            } else {
                set mat($i,$j) [tcl::mathop::+ $mat($i,$jvalue) $mat($ivalue,$jvalue)]
            }
        }
    }

    return $mat($m,$n)
}

if {$argc != 2} {
    exit
}

set s1 [lindex $argv 0]
set s2 [lindex $argv 1]

set r [findSubsequenceCount $s1 $s2]
puts "Output: $r"