编程沙龙（12）
IT商界
本月的题目：对于任意两个字符串s1和s2(字符串中字符只限于26个小写的英文字母)的最长公共子序列lcs(s1,s2)是s1和s2中都出现的最长子序列。例如，tie是striped和tiger的最长公共子序列。
本期参与答题的朋友非常多，但做对的朋友就不像上期“8个棋子”的题目那么多了。我分析了一下，有不少朋友是因为题目没有弄明白。比如我们讲的是子序列，自然是要有顺序的概念，“ti”和“it”的最长公共子序列就应是“t”或者“i”，所以如果只是把两个字符串的公共字符找出来那是不正确的。另外，像上期沙龙里我们分析的程序里，作者就是对问题没有考虑全面。
言归正传，下面我们来看看这个问题究竟应该怎么解决。
接着上期沙龙的分析，我们似乎有些进退两难了，是不是只有用穷举搜索的方法，才能解决这个问题呢？我们把其中s1的所有子序列都找出来，再去检验这些子序列是不是也是s2的子序列，以此来确定s1、s2的所有公共子序列，并且从中挑选出最长的。例如，s1中有N个字符，那它所有的子序列数应该是2N(包括一个空序列)。看起来好像还不错，只要在s2中检验这2N个子序列，问题应该就能够被解决。但我想这应该不是个好办法，因为随着字符串长度的增加，进行穷举搜索的时间可要以指数形式增长呀！
下面还是由我来给出常规的解题思路。首先我们假设A=
1.若ai=bj，则ck= ai=bj且{c1,c2…ck-1}是{a1,a2…ai-1}和{b1,b2…bj-1}的最长公共子序列。
2.若ai≠bj且ck≠ai，则C是{a1,a2…ai-1}和{b1,b2…bj}的最长公共子序列。
3.若ai≠bj且ck≠bj则C是{a1,a2…ai}和{b1,b2…bj-1}的最长公共子序列。
第一条结论应该很好理解。第二条如果结论不成立，那么A、B必然也有一个比C长的公共子序列，这和我们的假设矛盾，所以这条结论是正确的。第三条和第二条类似。
这样我们可以知道，两个序列的最长公共子序列包含了分别以这两个序列为前缀的两个序列的最长公共子序列。由此可得出解题的方法可以是利用递归方法从后往前搜索最长公共子序列。
当ai=bj时，找出
以下是用VB写成的找最长公共子序列的函数代码。
Public Function GetLCS(s1 As String, s2 As String) As String
Dim i As Long
Dim j As Long
Dim temp1 As String
Dim temp2 As String
i = Len(s1)
j = Len(s2)
If i = 0 Or j = 0 Then
GetLCS = ""
Exit Function
End If
If Mid(s1, i, 1) = Mid(s2, j, 1) Then
If (i = 1) Or (j = 1) Then
GetLCS = Mid(s1, i, 1)
Else
temp1 = Mid(s1, 1, i - 1)
temp2 = Mid(s2, 1, j - 1)
GetLCS = GetLCS(temp1, temp2) + Mid(s1, i, 1)
End If
Else
temp1 = Mid(s1, 1, i - 1)
temp2 = Mid(s2, 1, j - 1)
temp1 = GetLCS(temp1, s2)
temp2 = GetLCS(s1, temp2)
If Len(temp1) >= Len(temp2) Then
GetLCS = temp1
Else
GetLCS = temp2
End If
End If
End Function
我们将对本题精选出来的源代码提供下载。下载地址是http://paladin.nease.net/cpcw/lcs.zip