LCS問(wèn)題就是求兩個(gè)字符串最長(zhǎng)公共子串的問(wèn)題。解法就是用一個(gè)矩陣來(lái)記錄兩個(gè)字符串中所有位置的兩個(gè)字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對(duì)角線最長(zhǎng)的1序列，其對(duì)應(yīng)的位置就是最長(zhǎng)匹配子串的位置。

　　下面是字符串21232523311324和字符串312123223445的匹配矩陣，前者為X方向的，后者為Y方向的。不難找到，紅色部分是最長(zhǎng)的匹配子串。通過(guò)查找位置我們得到最長(zhǎng)的匹配子串為：21232


　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

　　但是在0和1的矩陣中找最長(zhǎng)的1對(duì)角線序列又要花去一定的時(shí)間。通過(guò)改進(jìn)矩陣的生成方式和設(shè)置標(biāo)記變量，可以省去這部分時(shí)間。下面是新的矩陣生成方式：

　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
　　1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
　　0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
　　1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

　　不用多說(shuō)，你大概已經(jīng)看出來(lái)了。當(dāng)字符匹配的時(shí)候，我們并不是簡(jiǎn)單的給相應(yīng)元素賦上1，而是賦上其左上角元素的值加一。我們用兩個(gè)標(biāo)記變量來(lái)標(biāo)記矩陣中值最大的元素的位置，在矩陣生成的過(guò)程中來(lái)判斷當(dāng)前生成的元素的值是不是最大的，據(jù)此來(lái)改變標(biāo)記變量的值，那么到矩陣完成的時(shí)候，最長(zhǎng)匹配子串的位置和長(zhǎng)度就已經(jīng)出來(lái)了。

　　這樣做速度比較快，但是花的空間太多。我們注意到在改進(jìn)的矩陣生成方式當(dāng)中，每生成一行，前面的那一行就已經(jīng)沒(méi)有用了。因此我們只需使用一維數(shù)組即可。最終的代碼如下：

Private Function LCS(ByVal str_1 As String, ByVal str_2 As String) As String
　　If str_1 = "" Or str_2 = "" Then Return ""

　　Dim c(str_1.Length) As Integer
　　Dim max, maxj, i, j As Integer
　　maxj = 0 : max = 0 '這兩個(gè)是標(biāo)志變量
　　For i = 0 To str_2.Length - 1
　　For j = str_1.Length - 1 To 0 Step -1
　　If str_2.Chars(i) = str_1.Chars(j) Then
　　If i = 0 Or j = 0 Then
　　c(j) = 1
　　Else
　　c(j) = c(j - 1) + 1
　　End If
　　Else
　　c(j) = 0
　　End If
　　If c(j) > max Then '把>改成>=則返回最后一個(gè)最長(zhǎng)匹配子串
　　max = c(j) : maxj = j '更新標(biāo)志變量
　　End If
　　Next
　　Next

　　If max = 0 Then Return ""
　　Return str_1.Substring(maxj - max + 1, max) '直接從標(biāo)志變量得出結(jié)果
　　End Function
　　這里的問(wèn)題大概你也看出來(lái)了：如果有多個(gè)最長(zhǎng)的匹配子串怎么辦呢？我這里只能是返回第一個(gè)。稍微改一下可以變成返回最后一個(gè)。要完整地返回所有最長(zhǎng)匹配子串，就需要一個(gè)標(biāo)志變量的數(shù)組了。你有興趣改改嗎？