动态规划求解最长公共子串中的问题

    今天学习了动态规划的相关思想，随后找了一些经典的题目希望能加深一下印象。然而在求解“最长公共子串”的问题时却发现了一些问题。

    一般来说，在求解这类问题的时候，大都依据以下原理：

    定义lcs[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，计算lcs[i]     [j]可递归地表述如下：

    （1）lcs[i][j] = 0                         如果i=0或j=0；
    （2）lcs[i][j] = lcs[i-1][j-1]+1             如果i,j>0，且a[i-1] = b[j-1]；
    （3）lcs[i][j] = max{lcs[i][j-1], lcs[i-1][j]} 如果i,j>0，且a[i-1] != b[j-1]。

      依据以上公式写出程序以后，在测试时发现对于输入串“ABCDDAB”和“BCDAB”所求得的最长公共子串为“BCDAB”，长度为5。但是我们可以很容易看出最长公共子串的长度应该为3，为“BCD”或“DAB”。经过检查代码，发现问题还是出在上述的状态转移公式中。当a[i-1] = b[j-1]时，lcs[i][j] = lcs[i-1][j-1]+1并不一定成立，因为lcs[i-1][j-1]的公共子串中并不一定包含a[i-1]和b[j-1]。例如对于上述输入串，a[6-1]=b[4-1],但是lcs[6][4]=3!=lcs[5][3]+1。

      目前找到网上的大部分求解方法都是基于上述公式，为什么会出现这么大的漏洞。难道是我理解错了？

 

 

     经过进一步的研究，发现我对于最长公共子串的理解有偏差。下面的内容引自：http://hxraid.iteye.com/blog/622462

     LCS：又称 最长公共子序列。 其中子序列(subsequence)的概念不同于串的子串。它是一个不一定连续 但按顺序取自字符串X中的字符序列。 例如：串"AAAG"就是串“CGATAATTGAGA”的一个子序列。

    字符串的相似性问题可以通过求解两个串间的最长公共子序列(LCS)来得到。

 

    对于最长公共子串问题的解法，参见http://space.itpub.net/16857/viewspace-79033。