算法导论OJ-最长公共子序列

一、原题目

1.题目描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad" ,顺次选1，3，5个字符就构成子串" cad" ,现给定两个字符串，求它们的最长共公子串。

2.输入

第一行两个字符串用空格分开。两个串的长度均小于2000 。

3.输出

输出一个整数，最长子串的长度。

4.样例输入

abccd aecd

5.样例输出

3

二、题目分析

经典的最长公共子序列问题，采用动态规划算法。

设问题输入的两个串为A和B。我们定义$dp[i][j]$表示$A[0:i]$与$B[0:j]$的最长公共子序列的长度。因此问题的解为$dp[lengthA][lengthB]$。

接下来给出动态规划的状态转移方程分析：

• 当$i==0$或$j==0$时，易知$dp[i][j]=0$。
• 当$A[i]==B[j]$时，由于$A[i]$与$B[j]$相同，那么$A[0:i]$与$B[0:j]$的最长公共子序列的长度$dp[i][j]$等于$A[0:i-1]$与$B[0:j-1]$的最长公共子序列的长度 + 1。即
  $$dp[i][j]=dp[i-1][j-1]+1$$
• 当$A[i]!=B[j]$时，只需从$A[0:i-1]$与$B[0:j]$与$A[0:i]$与$B[0:j-1]$中挑出最大值。即
  $$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$$

只需从头遍历，将对应值填入$dp[][]$即可求得最终解。

三、代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>

using namespace std;

string a, b;

int main()
{
	cin>>a>>b;
	int lengthA = a.size();
	int lengthB = b.size();
	vector<vector<int>> dp(lengthA + 1, vector<int>(lengthB + 1, 0));
	vector<vector<int>> tb(lengthA + 1, vector<int>(lengthB + 1, 0));
	for(int i = 1; i <= lengthA; i++){
		for(int j = 1; j <= lengthB; j++){
			if(a[i - 1] == b[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	cout<<dp[lengthA][lengthB]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28