C - 最长公共子序列
2024-09-08 04:21:40
C - 最长公共子序列
Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)
Problem Description
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在严格上升的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b,c, f, b, c >的子序列。
现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。Input
输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。
Output
对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。
Sample Input
abcfbc abfcab
programming contest
abcd mnpSample Output
4
2
0
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; char a[], b[];
int dp[][]; // 全局定义才会初始化为0 int main(){
while(~scanf("%s%s", (a+), (b+))){ //多组输入
int lena = strlen(a+), lenb = strlen(b+);
// 全部用(a+1) 是让字符串储存在下标[1, n]
// 下标从1开始,因为下面有访问dp[i-1][j] 防止越界
for(int i=; i <= lena; i++){
for(int j=; j <= lenb; j++){
dp[i][j] = max(dp[i-][j], dp[i][j-]); // 直接继承于当前位不用匹配的状态
if(a[i] == b[j]) { // 如果当前位可以匹配
dp[i][j] = max(dp[i][j], dp[i-][j-] + ); // 取一个max值
}
}
} printf("%d\n", dp[lena][lenb]); // 输出匹配长度
} }
最新文章
- 3dmax模型制作备忘录
- ImageView的常用属性
- iOS动画实现改变frme和contenOffset
- jquery-通过js编写弹出窗口
- Shell编程中括号判断中赋值语句和判断语句
- Redis部分数据结构方法小结
- pthread_barrier_init,pthread_barrier_wait简介
- angularjs 遇到Error: [$injector:unpr] Unknown provider: tdpicnews-serviceProvider <;- tdpicnews-service <;- tdpic-controller 错误
- MessageFormat类别:快速格式化字符串
- windows下npm scripts不能执行的问题
- Android自定义View(LineBreakLayout-自动换行的标签容器)
- java获取ip的方式,注意多级代理的方式获取
- 1.6Eigen中系数运算Reductions, visitors and broadcasting
- .NET 日期数据的格式化方法
- java web各个技术细节总结
- Async异步编程入门示例
- Upload文件时出现";Cannot access a closed file";错误
- RabbitMQ入门_10_队列长度限制
- JS中回调函数的使用
- thinkphp模型创建