动态规划经典——最长公共子序列问题 (LCS)和最长公共子串问题

时间:2021-06-01 03:18:46

一.最长公共子序列问题(LCS问题)

给定两个字符串A和B,长度分别为m和n,要求找出它们最长的公共子序列,并返回其长度。例如:

  A = "HelloWorld"

    B = "loop"

则A与B的最长公共子序列为 "loo",返回的长度为3。此处只给出动态规划的解法:定义子问题dp[i][j]为字符串A的第一个字符到第 i 个字符串和字符串B的第一个字符到第 j 个字符的最长公共子序列,如A“app”,B“apple”dp[2][3]表示 “ap” 和 “app” 的最长公共字串。注意到代码中 dp 的大小为 (n + 1) x (m + 1) ,这多出来的一行和一列是第 行和第 列,初始化为 0,表示空字符串和另一字符串的子串的最长公共子序列,例如dp[0][3]表示  "" 和 “app” 的最长公共子串。

当我们要求dp[i][j],我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]B[j -1]是否相同,如果相同它就是dp[i-1][j-1]+ 1,相当于在两个字符串都去掉一个字符时的最长公共子序列再加 1;否则最长公共子序列dp[i][j - 1] dp[i - 1][j]中大者。所以整个问题的初始状态为:
 $$ dp[i][0] =0 , dp[0][j] = 0$$
相应的状态转移方程为:
$$  dp[i][j] = \begin{cases} \max\{dp[i - 1][j],dp[i][j - 1]\} ,& {A[i - 1]  != B[j - 1]} \\ dp[i - 1][j - 1] + 1 , & {A[i - 1]  == B[j - 1]} \end{cases}  $$
代码的实现如下:
class LCS
{
public:
int findLCS(string A, int n, string B, int m)
{
if(n == 0 || m == 0)//特殊输入
return 0;
int dp[n + 1][m + 1];//定义状态数组
for(int i = 0 ; i <= n; i++)//初始状态
dp[i][0] = 0;
for(int i = 0; i <= m; i++)
dp[0][i] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j<= m; j++)
{
if(A[i - 1] == B[j - 1])//判断A的第i个字符和B的第j个字符是否相同
dp[i][j] = dp[i -1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
}
return dp[n][m];//最终的返回结果就是dp[n][m]
}
};

该算法的时间复杂度为O(n*m),空间复杂度为O(n*m)。此外,由于遍历时是从下标1开始的,因为下标为0表示空字符串;所以第A的第i个字符实际上为A[i -1],B的第j个字符为B[j-1]。

二.最长公共子串问题

给定两个字符串A和B,长度分别为m和n,要求找出它们最长的公共子串,并返回其长度。例如:

  A = "HelloWorld"

    B = "loop"

则A与B的最长公共子串为 "lo",返回的长度为2。我们可以看到子序列和子串的区别:子序列和子串都是字符集合的子集,但是子序列不一定连续,但是子串一定是连续的。同样地,这里只给出动态规划的解法:定义dp[i][j]表示以A中第i个字符结尾的子串和B中第j个字符结尾的子串的的最大公共子串(公共子串实际上指的是这两个子串的所有部分)的长度(要注意这里和LCS的不同,LCS中的dp[i+1][j+1]一定是大于等于dp[i][j]的;但最长公共子串问题就不一定了,它的dp[i][j]表示的子串不一定是以A[0]开头B[0]开头的,但是一定是以A[i-1]、B[j-1]结尾的),同样地, dp 的大小也为 (n + 1) x (m + 1) ,这多出来的一行和一列是第 行和第 列,初始化为 0,表示空字符串和另一字符串的子串的最长公共子串。

当我们要求dp[i][j],我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同,如果相同它就是dp[i - 1][j- 1] + 1,相当于在两个字符串都去掉一个字符时的最长公共子串再加 1;否则最长公共子串取0。所以整个问题的初始状态为:

$$ dp[i][0] =0 , dp[0][j] = 0$$

相应的状态转移方程为:
$$  dp[i][j] = \begin{cases} 0 ,& {A[i - 1]  != B[j - 1]} \\ dp[i - 1][j - 1] + 1 , & {A[i - 1]  == B[j - 1]} \end{cases}  $$
代码的实现如下:
class LongestSubstring {
public:
int findLongest(string A, int n, string B, int m) {
if(n == 0 || m == 0)
return 0;
int rs = 0;
int dp[n + 1][m + 1];
for(int i = 0 ; i <= n; i++)//初始状态
dp[i][0] = 0;
for(int i = 0; i <= m; i++)
dp[0][i] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j<= m; j++)
{
if(A[i - 1] == B[j - 1])
{
dp[i][j] = dp[i -1][j - 1] + 1;
rs = max(rs,dp[i][j]);//每次更新记录最大值
} else//不相等的情况
dp[i][j] = 0;
}
return rs;//返回的结果为rs
}
};

该算法的时间复杂度为O(n*m),空间复杂度为O(n*m)。同样地,遍历下标也是从1开始的。不过关于最长公共子串问题,有几点需要注意下:

1.由于dp[i][j]不像LCS是个递增的数组,所以它在每次更新时需要同时更新最大值rs,且最后返回的结果是rs。而LCS中返回的直接就是dp[n][m]。

2.从代码上来看,两者的结构其实差不多,只不过状态转移方程有些小许的不同,分析过程也类似。

3.另外,关于这量两种问题还有更优的解法,不过本文主要是DP的思想去解决,当然其中还有对DP的优化,不过此处不再详述。

参考:https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a

   https://blog.csdn.net/u012102306/article/details/53184446