使用动态规划寻找最长公共子串

"动态规划求最大匹配子串的算法及实现" 动态规划是解决许多复杂问题的有效方法，尤其是在寻找最长公共子序列或最长公共子串的问题中。在本例中，我们将探讨如何使用动态规划来求解两个字符串的最大匹配子串。 首先，我们需要理解算法的核心思想。动态规划的核心是通过构建一个二维数组来存储子问题的解，并利用这些解来求解原问题。对于给定的两个字符串str1和str2，我们定义函数f(m, n)，表示以str1的第m个字符和str2的第n个字符结尾的最长公共子串的长度。 算法的关键在于状态转移方程。当str1的第m+1个字符与str2的第n+1个字符相同时，我们可以将当前字符添加到公共子串中，因此f(m+1, n+1) = f(m, n) + 1；否则，如果字符不相同，那么不存在这样的公共子串，所以f(m+1, n+1) = 0。边界条件是f(0, j) = 0和f(j, 0) = 0，这意味着空字符串与任何字符串的最长公共子串都是空字符串。 接下来，我们看算法的实现部分。在C++代码中，首先计算两个字符串的长度，并动态分配一个二维整数数组pf来作为辅助空间。数组的大小为(len1+1)×(len2+1)，这是因为我们需要存储从0开始的索引。然后，初始化数组的第一行和第一列，将其值设为0，因为一个字符串与空字符串的最长公共子串长度为0。 接着，通过两层循环遍历数组的其余元素。在循环中，我们比较str1和str2对应位置的字符。如果字符相同，就更新pf[row][col]的值，并且检查是否超过了当前的最大公共子串长度，如果是，则更新最大值。如果字符不同，pf[row][col]则设置为0。 最后，释放辅助空间，返回最大公共子串的长度。在给出的例子中，输入的两个字符串分别为"blog.csdn.net"和"csdn.blog"，输出的二维数组表示了它们的最长公共子串长度，最终得出最长公共子串为"csdn"，长度为4。 总结，动态规划求最大匹配子串的算法是一种高效的方法，其时间复杂度为O(len1 * len2)，其中len1和len2分别为两个字符串的长度。它通过存储子问题的解避免了重复计算，从而提高了效率。