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”是指北京大学在线判题系统POJ上的一道编程题目,其核心任务是寻找一个序列中最长的有序子序列。描述中的“解题报告+AC代码”表明这个压缩包包含了对这道问题的解答思路...
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
动态规划 poj Common Subsequence c++ cpp文件
poj 2744子串 答案 所用的是最简单的C语言
【POJ 2774】要求求出两个字符串的最长公共子串,这可以通过后缀数组和LCP(Longest Common Prefix,最长公共前后缀)数组直接计算得出。 【POJ 3693】的问题更复杂一些,需要找出字符串中重复次数最多的连续重复子...
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
LMS Longest Monotonically Increasing Sequence Algorithm
在对齐问题中,可能需要找出两个字符串之间的最长公共子序列或最长公共子串,这是字符串处理中的经典问题。 4. **贪心算法**:另一种可能的解决方案是贪心策略,通过每次做出局部最优选择,期望得到全局最优解。...
3. **POJ1951**:可能与字符串的排序有关,比如可以运用Manacher's Algorithm解决最长回文子串问题,或者需要理解并实现Trie(字典树)数据结构以优化字符串查找。 4. **POJ2003**:这可能是一个关于字符串编辑距离...
* 1458 Common Subsequence:本题目使用动态规划来计算两个序列的最长公共子序列。 * 1579 Function Run Fun:本题目使用动态规划来计算函数的执行次数。 * 1887 Testing the CATCHER:本题目使用动态规划来计算测试...
6. 1458 Common Subsequence:寻找两个字符串的最长公共子序列,经典动态规划问题。 7. 1953 World Cup Noise:可能需要计算某种状态的最大可能性。 其次,模拟题通常是指通过精确复制问题的逻辑来求解的题目,这类...
包括最长公共子序列、最优二分检索树等问题,关键在于状态转移方程的设计。 ### 六、数学 #### 组合数学 涵盖加法原理、乘法原理、排列组合等,用于解决计数问题,如poj3252。 #### 数论 涉及素数检测、整除性、...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...
标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...