`
kenby
  • 浏览: 724595 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

poj 1458 最长公共子串(Longest Common Subsequence)

 
阅读更多

LCS问题:

给定序列

X = <x1,x2,...,xn>

和另一个序列

Y = <y1,y2,...,ym>

 

找两个递增的下标序列

<i1, i2, ...ik> 和 <j1, j2, ..., jk>使

xi1 == yj1

xi2 == yj2

......

xik == yjk

令Z = <xi1, xi2,..., xik>,那么称Z是X和Y的一个公共子串,

LCS问题是求最长的公共子串,即最长的下标序列

 

动态规划解法:

令Xi表示X的前缀<x1,x2,...,xi>

c[]i[j] 表示Xi和Yi的LCS长度,动态规划的状态转移方程为:

如果xi == yj, c[i][j] = c[i-1][j-1] + 1 

如果xi != yj,      c[i][j] = max(c[i-1][j], c[i][j-1])

 

#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define max(a,b) (a) > (b) ? (a) : (b)

#define N 250

int 	c[N][N];

int lcs(char *s1, char *s2)
{
	int		i, j, n, m;

	n = strlen(s1);
	m = strlen(s2);

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (s1[i-1] == s2[j-1]) {
				c[i][j] = c[i-1][j-1] + 1;
			}
			else {
				c[i][j] = max(c[i][j-1], c[i-1][j]);
			}
			debug("c[%d][%d] = %d\n", i, j, c[i][j]);
		}
	}

	return c[n][m];
}

int main()
{
	char 	s1[N], s2[N];

	while (scanf("%s%s", s1, s2) != EOF) {
		debug("%s %s\n", s1, s2);
		printf("%d\n", lcs(s1, s2));
	}
	return 0;
}
分享到:
评论

相关推荐

    北大POJ2533-Longest Ordered Subsequence【O(nlogn)】

    北大POJ2533-Longest Ordered Subsequence【O(nlogn)】

    POJ2533-Longest Ordered Subsequence

    标题“POJ2533-Longest Ordered Subsequence”是指北京大学在线判题系统POJ上的一道编程题目,其核心任务是寻找一个序列中最长的有序子序列。描述中的“解题报告+AC代码”表明这个压缩包包含了对这道问题的解答思路...

    北大POJ2533-Longest Ordered Subsequence【O(n^2)】

    北大POJ2533-Longest Ordered Subsequence【O(n^2)】

    poj Common Subsequence c++

    动态规划 poj Common Subsequence c++ cpp文件

    poj 2744子串 答案

    poj 2744子串 答案 所用的是最简单的C语言

    后缀数组相关题解1

    【POJ 2774】要求求出两个字符串的最长公共子串,这可以通过后缀数组和LCP(Longest Common Prefix,最长公共前后缀)数组直接计算得出。 【POJ 3693】的问题更复杂一些,需要找出字符串中重复次数最多的连续重复子...

    poj经典动态规划题目解题报告

    poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...

    最长公共子序列Longest Monotonically Increasing Sequence Algorithm

    LMS Longest Monotonically Increasing Sequence Algorithm

    POJ1836-Alignment

    在对齐问题中,可能需要找出两个字符串之间的最长公共子序列或最长公共子串,这是字符串处理中的经典问题。 4. **贪心算法**:另一种可能的解决方案是贪心策略,通过每次做出局部最优选择,期望得到全局最优解。...

    string-problem(POJ).rar_POJ 19_poj

    3. **POJ1951**:可能与字符串的排序有关,比如可以运用Manacher's Algorithm解决最长回文子串问题,或者需要理解并实现Trie(字典树)数据结构以优化字符串查找。 4. **POJ2003**:这可能是一个关于字符串编辑距离...

    POJ各题算法分类和题目推荐 ACM必看

    * 1458 Common Subsequence:本题目使用动态规划来计算两个序列的最长公共子序列。 * 1579 Function Run Fun:本题目使用动态规划来计算函数的执行次数。 * 1887 Testing the CATCHER:本题目使用动态规划来计算测试...

    算法分类以及POJ题目分类

    6. 1458 Common Subsequence:寻找两个字符串的最长公共子序列,经典动态规划问题。 7. 1953 World Cup Noise:可能需要计算某种状态的最大可能性。 其次,模拟题通常是指通过精确复制问题的逻辑来求解的题目,这类...

    poj各种分类

    包括最长公共子序列、最优二分检索树等问题,关键在于状态转移方程的设计。 ### 六、数学 #### 组合数学 涵盖加法原理、乘法原理、排列组合等,用于解决计数问题,如poj3252。 #### 数论 涉及素数检测、整除性、...

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    POJ1159-Palindrome

    【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    poj的一些题目的代码

    查看“最长公共子序列”的代码,可以了解动态规划的应用;研究“二分查找”的实现,可以掌握二分法的精髓。此外,这些代码通常会遵循一定的编码规范,有助于提升编程风格和代码质量。 总的来说,这个资源对于想要...

Global site tag (gtag.js) - Google Analytics