 |
|
|
 首页 |
名片设计 CorelDRAW Illustrator AuotoCAD Painter 其他软件 Photoshop Fireworks Flash |
|
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置。 下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：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的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方法和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方法： 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 不用多说，你大概已经看出来了。当字符匹配的时候，我们并不是简朴的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判定当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。 这样做速度比较快，但是花的空间太多。我们注重到在改进的矩阵生成方法当中，每生成一行，前面的那一行就已经没有用了。因此我们只需使用一维数组即可。最终的代码如下： 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 \\\'这两个是标志变量 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 \\\'把>改成>=则返回最后一个最长匹配子串 max = c(j) : maxj = j \\\'更新标志变量 End If Next Next If max = 0 Then Return \"\" Return str_1.Substring(maxj - max + 1, max) \\\'直接从标志变量得出结果 End Function 这里的问题大概你也看出来了：假如有多个最长的匹配子串怎么办呢？我这里只能是返回第一个。轻微改一下可以变成返回最后一个。要完整地返回所有最长匹配子串，就需要一个标志变量的数组了。你有爱好改改吗？ 返回类别: 教程 上一教程: Microsoft .NET 框架常见问题（一） 下一教程: 如何判定当前操作系统是否为98/2000/XP 您可以阅读与"LCS问题算法之VB.net版"相关的教程: · Vb.Net问题集 · Vb.Net问题集 · VS.NET RC5无法创建Add-IN工程解决办法（其它问题也可参阅本办法） · 利用.NET框架简化发布和解决DLL Hell问题(2) · VB.net 调用带参数存储过程 |
  |
| 快精灵印艺坊 版权所有 |
首页 会员中心在线印刷在线编辑付款方式索取样品设计指南连锁门店
|
||
