首页 > 其他 > 详细

最长公共子序列

时间:2016-08-20 11:18:53      阅读:168      评论:0      收藏:0      [点我收藏+]

给定两个字符串,求它们最长公共子序列的长度。

例如:

s = "abcd", t = "becd"

输出3("bcd")

利用动态规划求解

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 char s[102],t[102];
 9 int dp[102][102];
10 
11 int main(int argc, char const *argv[])
12 {
13     //freopen("input.txt","r",stdin);
14     while(scanf("%s %s",s,t) != EOF) {
15         int n = strlen(s);
16         int m = strlen(t);
17         memset(dp, 0, sizeof(dp));
18         for(int i = 0; i < n; i++) { 
19             for(int j = 0; j < m; j++) {
20                 if(s[i] == t[j]) {
21                     dp[i+1][j+1] = dp[i][j] + 1;
22                 }
23                 else {
24                     dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
25                 }
26             }
27         }
28         printf("%d\n",dp[n][m]);
29     }
30     return 0;
31 }

 

最长公共子序列

原文:http://www.cnblogs.com/jasonJie/p/5789713.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!