首页 > 代码库 > uva10405-最长公共子序列
uva10405-最长公共子序列
题目链接 http://acm.hust.edu.cn/vjudge/problem/19201
解题思路
LCS
代码
#include<stdio.h>#include<string.h>#define MAX_LEN 1005char str[MAX_LEN], re[MAX_LEN];int dp[MAX_LEN];int main(){ str[0] = re[0] = ‘0‘; while(gets(str+1) && gets(re+1)) { memset(dp, 0, sizeof(dp)); int n = strlen(str) - 1; int m = strlen(re) - 1; int x; for(int i=1; i<=n; i++) { x = dp[0]; for(int j=1; j<=m; j++) { if(str[i] == re[j]) { int y = dp[j]; dp[j] = x + 1; x = y; } else { x = dp[j]; dp[j] = dp[j]>dp[j-1]?dp[j]:dp[j-1]; } } } printf("%d\n", dp[m]); } return 0;}
uva10405-最长公共子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。