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 解题报告+AC代码
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
动态规划 poj Common Subsequence c++ cpp文件
poj 2744子串 答案 所用的是最简单的C语言
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
LMS Longest Monotonically Increasing Sequence Algorithm
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码