两个字符串的最长公共子序列(C++动态规划)
2022/1/31 12:34:20
本文主要是介绍两个字符串的最长公共子序列(C++动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h> using namespace std; char a[200]; char b[200]; int f[201][201];//记录长度 char p[201][201];//记录公共字符 int m,n; void LCS(){ int i,j; for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(a[i-1] == b[j-1]){ //左上方存放的一直是公共字符 //通过左上方的值更新长度 //f[i][j]的值由f[i-1][j-1]更新; f[i][j] = f[i-1][j-1]+1; p[i][j] = 1;//左上方 } else if(f[i][j-1] > f[i-1][j]){ f[i][j] = f[i][j-1]; p[i][j] = 2;//左方 } else{ f[i][j] = f[i-1][j]; p[i][j] = 3;//正上方 } } } printf("最长公共子序列长度为:%d",f[m][n]); //遍历完成后f[m][n]存储的值为最大公共子序列长度 } //打印最长公共子序列 void printLCS(){ int i = m, j = n, k = f[m][n]; char s[200]; while(i > 0 && j > 0){ if(p[i][j] == 1){ s[k--] = a[i-1]; //i-1 从最后的一个元素开始逆序存入是s[]数组 i--; j--; } else if(p[i][j] ==2) j--; else i--; } printf("最长公共子序列为:"); for(int i=1;i<=f[m][n];i++) printf("%c",s[i]); } int main(){ scanf("%s %s",&a,&b); m = strlen(a); n = strlen(b); LCS(); printf("\n"); printLCS(); return 0; }
测试用例
asdfghjkl agj
这篇关于两个字符串的最长公共子序列(C++动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!