最长公共子序列和最长公共子串——C++

一、给定两个字符串S1和S2，求两个字符串的最长公共子序列的长度。 输入样例 ABCD AEBD 输出样例 3 解释 S1和S2的最长公共子序列为ABD，长度为3

思路 动态规划 LCS(m,n)表示S1[0…m)和S2[0…n)的最长公共子序列的长度 S1[m-1] == S2[n-1]: LCS(m, n) = 1 + LCS(m - 1, n - 1)； S1[m-1] != S2[n-1]: LCS(m, n) = max(LCS(m - 1, n), LCS(m, n - 1))。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution{
          
   
public:
	int max(int x, int y)
	{
          
   
		if (x <= y)
			return x;
		else
		{
          
   
			return y;
		}
	}
	//找出最长公共子序列的长度
	int lengthOflongestCommonSequence(string& str1, string& str2){
          
   
		int m = str1.length(), n = str2.length();
		if (m == 0 || n == 0)
			return 0;
		dp = vector<vector<int> >(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i < m + 1; ++i){
          
   
			for (int j = 1; j < n + 1; ++j){
          
   
				if (str1[i - 1] == str2[j - 1])
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		return dp[m][n];
	}
	// 找出所有的最长公共子序列
	// 这里形参lcs_str不可以为引用，这里需要每次调用lcs_str都重新生成一个对象
	void PrintAllLCS(string& str1, string& str2, int i, int j, string lcs_str){
          
   
		//i， j为str1和str2的长度
		while (i > 0 && j > 0){
          
   
			if (str1[i - 1] == str2[j - 1]){
          
   
				lcs_str = str1[i - 1] + lcs_str;
				--i;
				--j;
			}
			else{
          
   
				if (dp[i - 1][j] > dp[i][j - 1])  //str1向前走
					--i;
				else if (dp[i - 1][j] < dp[i][j - 1])  //str2向前走
					--j;
				//str1和2向前均为LCS的元素
				else{
          
   
					PrintAllLCS(str1, str2, i - 1, j, lcs_str);
					PrintAllLCS(str1, str2, i, j - 1, lcs_str);
					return;
				}
			}
		}
		all_lcs.insert(lcs_str);
	}
	vector<vector<int>> dp;
	set<string> all_lcs;
};

int main()
{
          
   
    string s1 = "abcfbc";
    string s2 = "abfcab";
    Solution fir;
    string lcs_str;
    int res = fir.lengthOflongestCommonSequence(s1, s2);
    cout << res << endl;
    fir.PrintAllLCS(s1, s2, s1.length(), s2.length(), lcs_str);
    set<string>::iterator iter = fir.all_lcs.begin();
	while (iter != fir.all_lcs.end()) {
          
   
		cout << *iter++ << endl;
	}
    return 0;
}
/*
4
abcb
abfb
abfc
*/

二、求两个字符串的最长公共子串，要求子串连续 输入例子: bab caba 输出例子: 2 思路 动态规划 dp(m,n)表示S1[0…m)和S2[0…n)的最长公共子串的长度 当S1[m-1]==S2[n-1]: dp(m,n)=1+dp(m−1,n−1)； 当S1[m-1]!=S2[n-1]: dp(m,n) = 0。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
          
   
public:
	//输出最长公共子串的长度
	int lengthOflongestCommonSubstring(string& str1, string& str2){
          
   
		int m = str1.size(), n = str2.size();
		int res = 0;
		vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= m; ++i){
          
   
			for (int j = 1; j <= n; ++j){
          
   
				if (str1[i - 1] == str2[j - 1])
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else
					dp[i][j] = 0;
				if (res < dp[i][j])
					res = dp[i][j];
			}
		}
		return res;
	}
	//输出最长公共子串
	string LCS(string str1, string str2) {
          
   
		int m = str1.size();
		int n = str2.size();
		string res = "-1";
		int len = 0;
		int pos = 0;
		vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
		for (int i = 1; i <= m; i++)
		{
          
   
			for (int j = 1; j <= n; j++)
			{
          
   
				if (str1[i - 1] == str2[j - 1])
				{
          
   
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else
				{
          
   
					dp[i][j] = 0;
				}
				if (len < dp[i][j])
				{
          
   
					len = dp[i][j];
					pos = i;
				}
			}
		}
		if (len == 0)
		{
          
   
			return res;
		}
		res = str1.substr(pos - len, len);
		return res;
	}
};

int main()
{
          
   

}