poj-1458-Common Subsequence

简介: poj-1458-Common Subsequence


Common Subsequence

Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 43207
Accepted: 17522

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc         abfcab

programming    contest

abcd           mnp

Sample Output

4

2

0

Source

Southeastern Europe 2003



题目分析:

此题意思就是求最长子序列的长度,不管是否连续,这就是  lcs  


<span style="font-size:18px;">#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
  char str1[1010],str2[1010];
  int dp[1010][1010];
  while(~scanf("%s%s",str1,str2))
  {
    memset(dp,0,sizeof(dp));
    int len1=strlen(str1);
    int len2=strlen(str2);
    for(int i=1;i<=len1;i++)
    {
      for(int j=1;j<=len2;j++)
      {
        if(str1[i-1]==str2[j-1])
        {
          dp[i][j]=dp[i-1][j-1]+1;
        }
        else  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      }
    }
    printf("%d\n",dp[len1][len2]);
  }
  return 0;
}</span>





目录
相关文章
|
开发者
「代码强迫症?」从0到1实现项目代码拼写检查 vscode 插件:project-spell-checker(一)
「代码强迫症?」从0到1实现项目代码拼写检查 vscode 插件:project-spell-checker(一)
503 0
|
弹性计算 负载均衡 网络协议
负载均衡(SLB)使用最佳实践
负载均衡(Server Load Balancer,下文简称 SLB)的引入,可以降低单台云服务器 ECS(下文简称 ECS)出现异常时对业务的冲击,提升业务的可用性。同时,结合弹性伸缩服务,通过动态调整后端服务器,可以快速对业务进行弹性调整(扩容或缩容),以快速应对业务的发展。
14690 0
|
12月前
|
人工智能 自然语言处理 前端开发
💻2024 年值得一试的 8 个开发者工具💡
在本文中,我们精选了8款开发人员必备的高效工具,包括Webcrumbs、Pieces.app、Warp、Raycast等。这些工具涵盖了从前端插件生成、代码片段管理到多语言界面构建等多种功能,帮助开发人员简化工作流程、提高生产力。无论您是经验丰富的开发者,还是刚入行的新手,这些工具都将为您的开发过程带来效率提升和便利。探索这些工具,让您的开发工作更加轻松高效!
971 66
|
12月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
348 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
前端开发 小程序
微信小程序系列——无缝引入CSS或者WXML文件
微信小程序系列——无缝引入CSS或者WXML文件
|
Kubernetes 安全 Linux
容器运行时的内部结构和最新趋势(2023)下
容器运行时的内部结构和最新趋势(2023)
633 0
[学习][记录] c++语言:从放弃到入门 <二>多态
[学习][记录] c++语言:从放弃到入门 <二>多态
|
存储 关系型数据库 Linux
vCenter 6.7部署(Windows环境)
vCenter 6.7部署(Windows环境)
vCenter 6.7部署(Windows环境)
|
Kubernetes Cloud Native 网络协议
微服务上云后本地如何联调?
微服务上云后本地如何联调?
403 0
|
存储 缓存 JSON
Redis实现分页+多条件模糊查询组合方案
Redis实现分页+多条件模糊查询组合方案
469 0