dzm

用户名：17160200112

访问量：33945

签　名：

等　　级
排　　名	68
经　　验	10351
参赛次数	0
文章发表	172
年　　龄	0
在职情况	学生
学　　校	大连东软信息学院
专　　业	电子信息工程

　　自我简介：

TA的其他文章

蓝桥杯2015年第六届真题-打印大X-题解（C++代码）
浏览：266

蓝桥杯2018年第九届真题-次数差-题解（C++代码）
浏览：225

蓝桥杯2018年第九届真题-等腰三角形-题解（C++代码）
浏览：832

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

蓝桥杯算法提高VIP-最长公共子序列-题解（C语言代码）

　　作者: dzm　　　　发表时间：2020-07-21 14:52:37 浏览：228　|　评论：0　

原题链接：蓝桥杯算法提高VIP-最长公共子序列

https://blog.csdn.net/qq_43424037/article/details/107029364 可以参考这个人的文章，文章后面还有她的视频讲解的链接，个人觉得她讲的蛮好的，声音也蛮好听的。      O(∩_∩)O哈哈~。
```
#include <iostream> 
using namespace std;

int f[1005][1005];
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	for(int i=1;i<=s1.size();i++)
	{
		for(int j=1;j<=s2.size();j++)
		{
			if(s1[i-1]==s2[j-1])
				f[i][j]=f[i-1][j-1]+1;
			else
				f[i][j]=max(f[i-1][j],f[i][j-1]);
		}
	}
	cout<<f[s1.size()][s2.size()];
	return 0;
}
```

此题可以扩展要求不仅求出最大串的长度，还需要求出最大的公共子串。

拓展后的解法为：

```
#include <iostream> 
using namespace std;

int f[1005][1005];
int vis[1005][1005];
string s1,s2;

void  step(int n,int m)
{
	if(n==0||m==0) return;
	if(vis[n][m]==1)
	{
		step(n-1,m-1);
		cout<<s1[n-1]<<" ";
	}
	else if(vis[n][m]==2)
		step(n-1,m);
	else if(vis[n][m]==3)
		step(n,m-1);
}

int main()
{
	cin>>s1>>s2;
	for(int i=1;i<=s1.size();i++)
	{
		for(int j=1;j<=s2.size();j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				f[i][j]=f[i-1][j-1]+1;
				vis[i][j]=1;  //  ↖ 
			}
			else if(f[i][j-1]<f[i-1][j])
			{
				f[i][j]=f[i-1][j];
				vis[i][j]=2; //  ↑
			}
			else
			{
				f[i][j]=f[i][j-1];
				vis[i][j]=3; //  ←
			}	
		}
	}	
	cout<<f[s1.size()][s2.size()]<<endl;
	step(s1.size(),s2.size());
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

dzm

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-统计字符（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

蓝桥杯算法提高VIP-最长公共子序列-题解（C语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

三角形（C++代码）记忆化搜索

简单的a+b （C语言代码）

Tom数（C语言代码）

整数平均值（C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

dzm

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C二级辅导-统计字符 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

蓝桥杯算法提高VIP-最长公共子序列-题解（C语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

三角形 （C++代码）记忆化搜索

简单的a+b （C语言代码）

Tom数 （C语言代码）

整数平均值 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-统计字符（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

三角形（C++代码）记忆化搜索

Tom数（C语言代码）

整数平均值（C语言代码）