首页 > 代码库 > 1006 最长公共子序列Lcs(经典动态规划)
1006 最长公共子序列Lcs(经典动态规划)
传送门
Description
给出两个字符串A B,求A与B的最长公共子序列(子序列不要求是连续的)。
Input
第1行:字符串A第2行:字符串B(A,B的长度 <= 1000)
Output
输出最长的子序列,如果有多个,随意输出1个。
Sample Input
abcicbaabdkscab
Sample Output
abca
思路
记:
Xi=﹤x1,?,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀)
Yj=﹤y1,?,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀)
假定Z=﹤z1,?,zk﹥∈LCS(X , Y) 。
若xm=yn(最后一个字符相同),则不难用反证法证明:该字符必是X与Y的任一最长公共子序列Z(设长度为k)的最后一个字符,即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时,问题化归成求Xm-1与Yn-1的LCS(LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1)。
若xm≠yn,则亦不难用反证法证明:要么Z∈LCS(Xm-1, Y),要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立,若zk≠xm则有Z∈LCS(Xm-1 , Y),类似的,若zk≠yn 则有Z∈LCS(X , Yn-1)。此时,问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为:max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。
由于上述当xm≠yn的情况中,求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度,这两个问题不是相互独立的:两者都需要求LCS(Xm-1,Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS,故问题具有最优子结构性质考虑用动态规划法。
也就是说,解决这个LCS问题,你要求三个方面的东西:
- 1、LCS(Xm-1,Yn-1)+1;
- 2、LCS(Xm-1,Y),LCS(X,Yn-1);
- 3、max{ LCS(Xm-1, Y),LCS(X, Yn-1) }。
最长公共子序列的结构
最长公共子序列的结构有如下表示:
设序列X=< x1, x2, …, xm >和Y=< y1, y2, …, yn >的一个最长公共子序列Z=< z1, z2, …, zk >,则:
- 若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;
- 若xm≠yn且zk≠xm ,则Z是Xm-1和Y的最长公共子序列;
- 若xm≠yn且zk≠yn ,则Z是X和Yn-1的最长公共子序列。
其中Xm-1 = < x1, x2, …, xm-1 >,Yn-1 = < y1, y2, …, yn-1 >,Zk-1 = < z1, z2, …, zk-1 >。
我们定义c[i, j]表示Xi和Yi的LCS的长度。如果i = 0或j = 0,即一个序列长度为0,那么LCS的长度为0.根据LCS问题的最优子结构性质,可得到如下公式:
0 | 若i = 0 或 j = 0 | ||
c[i, j] | = | c[i - 1,j - 1] + 1 | 若i, j > 0 且 xi = yi |
max(c[i, j - 1],c[i - 1, j]) | 若i, j > 0 且 xi≠yi |
#include<stdio.h>#include<string.h>const int maxn = 1005;int dp[maxn][maxn] = {0};int main(){ char a[maxn],b[maxn],lcs[maxn]; int i,j; scanf("%s",a);scanf("%s",b); int lena = strlen(a),lenb = strlen(b); for (i = 1;i <= lena;i++) { for (j = 1;j <= lenb;j++) { if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = dp[i][j-1]>dp[i-1][j]?dp[i][j-1]:dp[i-1][j]; } } i = lena,j = lenb; int len = dp[lena][lenb]; lcs[len] = ‘\0‘; while (dp[i][j]) { if (dp[i][j] == dp[i-1][j]) i--; else if (dp[i][j] == dp[i][j-1]) j--; else lcs[--len] = a[i-1],i--,j--; } printf("%s\n",lcs); return 0;}
1006 最长公共子序列Lcs(经典动态规划)