[转帖]POJ 1458 Common Subsequence_MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2045 | 回复: 0   主题: [转帖]POJ 1458 Common Subsequence        下一篇 
cc
注册用户
等级:中校
经验:1900
发帖:195
精华:0
注册:2011-7-25
状态:离线
发送短消息息给cc 加好友    发送短消息息给cc 发消息
发表于: IP:您无权察看 2015-1-7 16:07:44 | [全部帖] [楼主帖] 楼主

描述:
寻找两个字符串中的最长相同序列,不一定连续。
思路:
利用Dp,状态转移方程

1.C[i+1][j+1]+1 (X[i]=Y[j])

C[i][j] = 2.Max(C[i+1][j],C[i][j+1]) (X[i]!=Y[j])


相对来说是简单的dp入门题目。
实现代码:

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define N 10010
char X[N],Y[N];
int C[N][N];
void Solve(int m,int n)
{
      int i,j;
      for(i=0;i<=m;i++)
      {
            C[i][n]=0;
      }
      for(j=0;j<=n;j++)
      {
            C[m][j]=0;
      }
      for(i=m-1;i>=0;i--)
      {
            for(j=n-1;j>=0;j--)
            {
                  if(X[i]==Y[j])
                  {
                        C[i][j]=C[i+1][j+1]+1;
                  }
                  else
                  {
                        if(C[i+1][j]>C[i][j+1])
                        {
                              C[i][j]=C[i+1][j];
                        }
                        else
                        {
                              C[i][j]=C[i][j+1];
                        }
                  }
            }
      }
}
int main()
{
while(scanf("%s%s",X,Y)==2)
{
      int m=strlen(X);
      int n=strlen(Y);
      Solve(m,n);
      printf("%d\n",C[0][0]);
}
return 0;
}


--转自 北京联动北方科技有限公司




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论