文章

59

粉丝

0

获赞

286

访问

6.2k

头像
最长连续公共子序列 题解:dp[i][j]>=maxx
P1730 西安电子科技大学/南京大学机试题
发布于2026年3月18日 11:42
阅读数 84

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

int main()
{
	string s1, s2;
	int dp[101][101];
	while (cin >> s1 >> s2)
	{
		int l1=s1.size(),l2=s2.size();
		memset(dp,0,sizeof(dp));
		int maxx=0,pos=0;
		for(int i=1;i<=l1;i++)
			for(int j=1;j<=l2;j++)
			{
				if(s1[i-1]==s2[j-1])
				{
					dp[i][j]=dp[i-1][j-1]+1;
					if(dp[i][j]>=maxx)
					{
						maxx=dp[i][j];
					 	pos=i-maxx;
					}
				}
				else dp[i][j]=0;
			}
		cout<<maxx<<endl;
		for(int i=pos;i<pos+maxx;i++)
			cout<<s1[i];
		cout<<endl;
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发