“最长公共字符串子序列”问题的动态规划法算法.pdf

“最长公共字符串子序列”问题是一个经典的计算机科学问题，它涉及到字符串处理和动态规划算法。在本篇文档中，作者成晓旭详细介绍了如何通过动态规划法解决这一问题。 动态规划是一种有效的方法来解决此类问题，它通过构建一个二维数组（在这里是`substrlen`）来存储子问题的解，并逐步递归地构建出最终答案。在这个问题中，目标是找到两个给定字符串（`a`和`b`）的最长公共字符串子序列，即在不改变字符顺序的情况下，两个字符串中都存在的最长子序列。 `First_Born_SubStr_Len`函数是计算两个字符串的最长公共子序列长度的核心部分。这个函数首先初始化一个`substrlen`矩阵，其中`substrlen[i][j]`表示字符串`a`的前`i`个字符与字符串`b`的前`j`个字符之间的最长公共子序列的长度。然后，通过两层循环遍历整个矩阵，比较当前字符是否相等，如果相等则在之前找到的公共子序列长度基础上加1；如果不相等，则选择两个方向（左或上）中的较长子序列。 `Build_First_Born_SubStr`函数用于构造最长公共子序列本身。它从`First_Born_SubStr_Len`得到的长度和矩阵`array`出发，通过回溯找出具体的子序列。这个过程逆向进行，从矩阵的右下角（即最长公共子序列的结束位置）开始，直到到达左上角（长度为0的位置）。 `Run_SubString`函数是测试上述算法的入口，它接收用户输入的两个字符串，调用`Build_First_Born_SubStr`函数并打印出最长公共子序列。 在`main`函数中，虽然代码没有完全给出，但通常会调用`Run_SubString`来进行实际运行和测试。这个例子展示了动态规划如何用于解决实际问题，并提供了一个易于理解的实现。 动态规划法在解决“最长公共字符串子序列”问题上表现出高效率和简洁性，避免了不必要的重复计算。这个算法可以扩展到更复杂的字符串操作和序列比对场景，例如生物信息学中的DNA序列比对。