Common Subsequence
Time Limit: 1000MS
|
|
Memory Limit: 10000K
|
Total Submissions: 17815
|
|
Accepted: 6847
|
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
解题思路:这是个求最长公共子序列长度的问题,首先要知道子序列不一定必须是连续的,即中间可以被其他字符分开,但它们的顺序必须是正确的。另外,最长公共子序列不一定只有一个,而我们要寻找的是其中之一就够了。
此题是典型的动态规划问题,我们先考虑输入序列S1和S2的前缀序列:
设c[i, j] = |LCS(S1[1..i], S2[1..j])|,则有c[m, n] = |LCS(S1, S2)|。
仔细观察我们可以发现递推式:
c[i, j] = c[i-1, j-1] + 1, 如果S1[i] = S2[j]
=max{c[i-1, j], c[i, j-1]}, 如果S1[i] != S2[j]
因此我们获得了该问题的最优子结构特性,即一个最优解决方案包含了子问题的最优解决方案,也就是说,如果CS=LCS(S1, S2),则CS的任何前缀子串必是S1和S2的某个前缀的最长公共子序列。
通过分析我们还可以知道该递归包含了重复的子问题,因此我们就可以使用DP来降低复杂度。
计算最长公共子序列长度的DP算法如下:
初始化c[i, j],0<=i<=m, 0<=j<=n
for i=1 to m do
for j=1 to n do
if S1[i]==S2[j] then
c[i, j] = LCS[S1, S2, i-1, j-1] + 1 (即c[i-1, j-1] + 1)
else if c[i-1, j] <= c[i, j-1] then
c[i, j] = c[i, j-1]
else
c[i, j] = c[i-1, j]
代码如下:
#include <iostream>
#include <string>
std::string str1;
std::string str2;
int num[256][256]; //数组开低了会出现Runtime Error
int lcs(std::string s1, std::string s2, int m, int n)
{
for(int i=1; i<=m; i++)//此处需从1开始,因为下面循环有num[i-1][j-1]是最小的
{
for(int j=1; j<=n; j++)
{
if(s1[i-1] == s2[j-1])
{
num[i][j] = num[i-1][j-1] + 1;
}
else
{
if(num[i][j-1] < num[i-1][j])
{
num[i][j] = num[i-1][j];
}
else
{
num[i][j] = num[i][j-1];
}
}
}
}
return num[m][n];
}
int main()
{
int len1, len2;
while(std::cin>>str1>>str2)
{
memset(num, 0, sizeof(num));
len1 = str1.length();
len2 = str2.length();
int out = lcs(str1,str2,len1,len2);
std::cout<<out<<std::endl;
}
system("pause");
return 0;
}
分享到:
相关推荐
最长公共子序列Longest Common Subsequence - Super Jiju的小窝_ To be with my Dearest Jessie
动态规划 poj Common Subsequence c++ cpp文件
Finding Maximum Contiguous Subsequence Sum using divide-and-conquer approach
Pku acm 第1458题 Common Subsequence 代码,有详细的注释,动态规划
最大子序列和该算法采用向量(数组)并找到它的最大子序列和: node max-subsequence-sum.js [2,-4,6,8,-10,100,-6,5]
算法设计类源码。使用动态规划的方式计算两个字符串的最大公共子序列。
LCS Longest (maximum) common subsequence
最长公共子序列问题,动态规划法
最大子序列和算法的运行时间 衡量执行时间
Common Subsequence 动态规划 java(csdn)————程序
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
A program to compute longest common subsequence between two sequences but in linear space. 2. Constrained LCS. Given two sequences X, Y and a constrained sequence P, a sequence Z is a constrained ...
最长公共子序列 这是一个实施动态编程以查找最长公共子序列的项目,该项目已作为ITCS-6114 / 8114:算法和数据结构课程的一部分进行。 程序和数据结构设计:给定的项目被编写为3个单独的程序。...
java动态规划的最长公共子序列算法和最长递增子序列算法
leetcode 2 和 c 面试 3月25日至3月31日 3月25日 1. Learn about ...https://www.geeksforgeeks.org/common-divisors-of-n-numbers/ ...https://leetcode.com/problems/is-subsequence/ - Done 3. Coursera - algori