C/C++之最长公共子序列

最长公共子序列

给定两个字符串，输出最长公共子序列，如输入

AB34C A1BC2 输出 ABC

#include<iostream>
#include<algorithm>
using namespace std;
string s1,s2;
int len1,len2;
int dp[1000][1000];
int flag=0;
string parseDp(string s1,string s2)
{
          
   
	string str;
	int M=len1;
	int N=len2;
	while(M>0&&N>0)
	{
          
   
		if(dp[M][N]>max(dp[M-1][N],dp[M][N-1]))
		{
          
   
			str+=s1[M-1];
			M--;
			N--;
		}
		else
		{
          
   
			if(dp[M-1][N]>dp[M][N-1])
				M--;
			else
				N--;
			
		}
	}
	reverse(str.begin(),str.end());
	return str;
}
string solution(string s1,string s2)
{
          
   
	for(int i=1;i<=len1;i++)
	{
          
   
		if(flag)
		{
          
   
			dp[i][1]=1;
		}
		else if(s1[i-1]==s2[0])
		{
          
   
			dp[i][1]=1;
			flag=1;
		}
		else
			dp[i][1]=0;
	}
	flag=0;
	for(int j=1;j<=len2;j++)
	{
          
   
		if(flag)
		{
          
   
			dp[1][j]=1;
		}
		else if(s2[j-1]==s1[0])
		{
          
   
			dp[1][j]=1;
			flag=1;
		}
		else
			dp[1][j]=0;
	}
	for(int i=2;i<=len1;i++)
	{
          
   
		for(int j=2;j<=len2;j++)
		{
          
   
			int maxOfLeftAndUp=max(dp[i-1][j],dp[i][j-1]);
			if(s1[i-1]==s2[j-1])
			{
          
   
				dp[i][j]=max(maxOfLeftAndUp,dp[i-1][j-1]+1);
			}
			else
				dp[i][j]=maxOfLeftAndUp;
		}
	}
	return parseDp(s1,s2);
}
int main()
{
          
   
	cin>>s1>>s2;
	len1=s1.length();
	len2=s2.length();
	cout<<solution(s1,s2);
	return 0;
}