首页 > 其他 > 详细

LCS

时间:2016-09-11 17:14:02      阅读:112      评论:0      收藏:0      [点我收藏+]
2016-09-11 16:37:13

代码

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 int dp[1010][1010]={0};
 6 int main()
 7 {
 8     char a[1010],b[1010],c[1010];
 9     int la,lb,lc;
10     scanf("%s",a);
11     scanf("%s",b);
12     la=strlen(a);
13     lb=strlen(b); 
14     int i,j,k=0;
15     for(i=1;i<=la;i++)
16     for(j=1;j<=lb;j++)
17     {
18         if(a[i-1]==b[j-1])
19             dp[i][j]=dp[i-1][j-1]+1;
20         else
21             dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
22     }
23     for(i=la,j=lb;i>=1&&j>=1;)
24     {
25         if(a[i-1]==b[j-1])
26         {
27             c[k++]=a[i-1];
28             i--;j--;
29         }
30         else
31         {
32             if(dp[i][j-1]>dp[i-1][j])
33                 j--;
34             else
35                 i--;
36         }
37         
38     }
39     for(k--;k>=0;k--)
40         printf("%c",c[k]);
41     printf("\n");
42     return 0;
43 }

 

LCS

原文:http://www.cnblogs.com/1778393206-qq/p/5862066.html

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