`

HDU 1159 Common Subsequence .

阅读更多

Common Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8893    Accepted Submission(s): 3578

Problem 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.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. 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
 

 

Recommend
Ignatius
 
呢个系DP既一种经典题型,叫LCS(Longest Common Subsequence)最长公共子序列,系允许吾连续,连续又系另外一种鸟。
首先就系要提到一种叫做最优子结构既性质,相当好用正斗既性质。
 
设X = <x1, x2, ........xm>, Xm-1 = <x1, x2, .........xm-1>
    Y = <y1, y2, ........yn>, Yn-1 = <y1, y2, .........yn-1>
    Z = <z1, z2, ........zk>, Zk-1 = <z1, z2, ........zk>
 
另外Z为X,Y既LCS,就可以引出如下性质:,
 
1、当xm = ym既时候, Zk-1为Xm-1同埋Yn-1既LCS。(因为zk就系xm(ym), 呢种情况Z = Zk-1 + 1)
2、当xm != ym既时候, Z就系 "Xm-1同Y” 或者  "X同Yn-1" 既LCS。(即系两种可能之间既最大值)
 
根据呢两个性质就可以即刻写出一个递归定义:
两个序列既LCS包含左两个序列前序既然LCS。
姐系甘,你要求XY既LCS,就首先要求出"Xm-1同 Yn-1"、 "Xm-1同Y” 或者  "X同Yn-1"既LCS。
写成递归式就系下面甘样:
 
设ts[i][j]储存Xi同Yi既LCS长度。
               {          ts[i][j] = 0                                           i = 0 || j = 0        //注意呢度可以解决空集情况
ts[i][j] = {           ts[i][j] = ts[i][j]                                     xi = yi
               {          ts[i][j] = Max(ts[i][j - 1], ts[i - 1][j])    xi != yi 
 
但系如果字符串好大, 写递归好明显吾得吃,所以用二维数组递推,时间复杂度O(n*m)。
 
下面系代码:
 
4226991 2011-07-20 15:59:19 Accepted 1159 62MS 24556K 952 B C++ 10SGetEternal{(。)(。)}!
 
#include <iostream>
#include <string>
using namespace std;

#define MAXF(x, y) (x > y? x: y)

string x, y;
int    lx, ly, **ts;

void print(int *arr, int siz)
{
 int i;

 for (i = 0; i < siz; i++)
  printf("%6d", arr[i]);
 putchar('\n');
}

void init()
{
 int i;
 
 lx = x.length();
 ly = y.length();
 ts = new int *[lx + 1];
 for (i = 0; i < lx + 1; i++)
 {
  ts[i] = new int [ly + 1];
  memset(ts[i], 0, sizeof(int) * (ly + 1));
#if 0
  print(ts[i], ly + 1);
#endif
 }
}

int dp()
{
 int i, j;
 
#if 0
 printf("test  = %d\n", MAXF(8, 7));
#endif
 for (i = 1; i <= lx; i++)
  for (j = 1; j <= ly; j++)
   if (x[i - 1] == y[j - 1])
    ts[i][j] = ts[i - 1][j - 1] + 1;
   else ts[i][j] = MAXF(ts[i][j - 1], ts[i - 1][j]);
 return ts[lx][ly];
}

int main()
{
 while (cin >> x >> y)
 {
#if 0
  printf("%s %s\n", x.c_str(), y.c_str());
#endif
  init();
  printf("%d\n", dp());
 }

 return 0;
}
 

 

 
搞掂{=      =+}
分享到:
评论

相关推荐

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    大学期间操作系统实验-HDU操作系统实验.zip

    HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...

    hangdianACM.rar_hangdiana_hdu acm_www.hangdianacm_杭电

    这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...

    HDU-ACM课件.rar

    HDU-ACM课件.rar 是一个专门为编程竞赛爱好者准备的资源包,主要涵盖了ACM(国际大学生程序设计竞赛)中常见的算法知识。这个压缩包包含了一系列与算法相关的主题,旨在帮助初学者理解和掌握基础及进阶算法。下面将...

    算法-数塔(HDU-2084).rar

    标题中的“算法-数塔(HDU-2084)”是指一个编程竞赛题目,源自杭州电子科技大学(HDU)的在线编程平台。在这个问题中,参赛者被要求解决一个名为“数塔”的算法挑战。数塔问题通常涉及到递归、深度优先搜索(DFS)...

    HDU-1535-.zip_多源点

    标题中的"HDU-1535-.zip_多源点"表明这是一个关于解决 ACM (国际大学生程序设计竞赛)问题的程序代码包,问题编号为 HDU 1535,且该问题涉及到多源点的最短路径计算。描述中提到的"求多源点到单终点的最短路(反向...

    算术(HDU-6715).rar

    标题中的“算术(HDU-6715)”很可能是指一个编程竞赛或在线教育平台上的一个问题或挑战,通常这类题目会涉及到算法和数学的应用。由于没有具体的标签信息,我们将根据题目标题和可能的内容来推测相关的IT知识点。 ...

    算法-确定比赛名次(HDU-1285).rar

    《算法-确定比赛名次(HDU-1285)》 算法是计算机科学的基础,也是解决复杂问题的关键工具。在这个问题中,我们聚焦于一个具体的算法挑战——确定比赛名次,这个问题来源于HDU(杭州电子科技大学)的在线编程竞赛...

    最短路(HDU-2544).rar

    《最短路问题详解》 在计算机科学领域,最短路问题是一个经典的图论问题,其目标是寻找网络中两点间路径的最小成本。这个问题在众多应用中都有所体现,如交通规划、通信网络设计、社交网络分析等。...

    数字图像处理总ppt_hdu_许老师.pdf

    数字图像处理是计算机科学和信息技术领域中的一种重要技术,涉及到图像处理、图像分析和图像识别等方面。下面是根据给定的文件信息生成的相关知识点: 1. 数字图像的定义和分类:数字图像是指使用数字信号表示的...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

Global site tag (gtag.js) - Google Analytics