最长公共子串问题：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子串就是求给定两个序列的一个最长公共子序列。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。 问题分析： 给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。 考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质： （1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列； （2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列； （3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。 这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个 最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列 和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。 为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法，具体说明如下。 定义c[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下： （1）c[i][j] = 0 如果i=0或j=0； （2）c[i][j] = c[i-1][j-1]+1 如果i,j0，且a[i-1] = b[j-1]； （3）c[i][j] = max{c[i][j-1], c[i-1][j]} 如果i,j0，且a[i-1] != b[j-1]。 按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以从c[m][n]开始，跟踪c[i][j]的产生过程，逆向构造出最长公共子序列。 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sharpdew/archive/2006/05/30/763180.aspx
在C语言中实现动态规划求解最长公共子串时，最关键的是理解状态转移方程。我们需要定义一个二维数组作为状态存储结构，例如dp表示以第一个字符串前i个字符和第二个字符串前j个字符结尾的最长公共子串长度。如果当前字符相同，那么dp=dp+1；否则dp=0。同时我们要维护一个变量max_len来记录过程中出现的最大值，最终结果就是这个max_len。这种思路在实际编写代码的时候需要注意索引处理和边界条件
实现动态规划解决最长公共子串问题时，首先需要明确子问题的定义，然后设计状态转移方程。在C语言中，通常会使用一个二维数组dp来保存中间结果，其中dp表示以第一个字符串的前i个字符和第二个字符串的前j个字符结尾的最长公共子串长度。当两个字符相等时，dp=dp+1；否则为0。通过不断更新最大值，我们可以最终得到最长公共子串的长度。虽然这种方法需要额外的空间，但对于初学者来说逻辑清晰且容易理解和实现
动态规划解决最长公共子串的问题其实挺直观的，核心思想就是用一个二维数组来记录两个字符串中各个字符之间的匹配情况。比如说，我们定义一个二维数组dp，表示第一个字符串的前i个字符和第二个字符串的前j个字符结尾的最长公共子串长度。如果两个字符相等的话，那么dp就等于dp+1，否则的话就是0。这样我们每次更新的时候都记录一下最大值，最后就能找到最长公共子串的长度了。不过要注意初始化的问题，特别是边界条件
最长公共子串问题用动态规划来做的话，关键是构建一个二维数组用来记录连续匹配的结果。举个例子来说，比如有两个字符串s1和s2，我们可以创建一个二维数组dp，其中dp代表以s1的第i个字符和s2的第j个字符结尾的最长公共子串长度。如果s1等于s2，那么dp=dp+1，否则就是0。通过遍历整个二维数组并记录最大值，就可以得到最长公共子串的长度。这种方法虽然空间复杂度是O(n*m)，但在C语言中实现起来也不算太难
举报成功
经过核实后将会做出处理
感谢您为社区和谐做出贡献
扫码参与新品0元试用
晒单、顶楼豪礼等你拿
