最长公共子序列问题——LCS算法
问题描述:
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。比如两个串为：abcicbaabdkscabab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。
输入格式:
第1行：字符串A 第2行：字符串B (A,B的长度 <= 1000)
输出格式:
输出最长的子序列，如果有多个，随意输出1个。
输入样例:
abcicbaabdkscab
输出样例:
abca
这题是典型的动态规划题型
●明确原始问题 C[n,m]：X[1,n]和Y[1,m]的最长公共子序列长度
●递推关系确立
推导过程：点击这里
伪码描述：
●Longest-Common-Subsequence(X,Y)
输入两个序列X,Y输出X和Y的最长公共子序列n<-length(X)m<-length(Y)//初始化新建二维数组C[0..n,0..m]和追踪二维数组rec[0..n,0..m]for i<-0 to n doC[i,0]<-0endfor j<-0 to m doC[0,i]<-0end//动态规划for i<-1 to n dofor j<-1 to m do//当X[i]=Y[i]时if X[i]=Y[i] thenC[i,j]<-C[i-1,j-1]+1rec[i,j]<-"LU"endelse if C[i-1,j]≥C[i,j-1] thenC[i,j]<-c[i-1,j]rec[i,j]<-"U"endelseC[i,j]<-C[i,j-1]rec[i,j]<-"L"endendendreturn C,rec
●Print-LCS(rec,X,i,j)
输入追踪数组rec,序列X,当前位置i和j输出X[1..i]和Y[1..j]的最长公共子序列if i=0 or j=0 then//终止递归return NULLend//三种递归式的情况if rec[i,j]="LU" thenPrint-LCS(rec,X,i-1,j-1)print x[i]endelse if rec[i,j]="U" thenPrint-LCS(rec,X,i-1,j)endelsePrint-LCS(rec,X,i,j-1)end
AC代码:
#include<stdio.h>#include<string.h>using namespace std;const int MAXSIZE=1001;int C[MAXSIZE][MAXSIZE];char rec[MAXSIZE][MAXSIZE];char X[MAXSIZE];char Y[MAXSIZE];void Initialization(int n,int m){//初始化for(int i=0;i<=n;i++)C[i][0]=0;for(int i=0;i<=m;i++)C[0][i]=0;}void Lcs(int n,int m){//LCS算法for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(X[i]==Y[j]){C[i][j]=C[i-1][j-1]+1;rec[i][j]='W';}else if(C[i-1][j]>=C[i][j-1]){C[i][j]=C[i-1][j];rec[i][j]='U';}else{C[i][j]=C[i][j-1];rec[i][j]='L';}}}}void Print_Lcs(int n,int m){//根据rec数组输出int i=n;int j=m;if(i==0||j==0)return;if(rec[i][j]=='W'){Print_Lcs(i-1,j-1);printf("%c",X[i]);}else if(rec[i][j]=='U'){Print_Lcs(i-1,j);}else{Print_Lcs(i,j-1);}}int main(){scanf("%s%s",X+1,Y+1);size_t n=strlen(X+1);size_t m=strlen(Y+1);Initialization(n,m);Lcs(n,m);Print_Lcs(n,m);}
