7-12 LCS (10 分)
Longest common subsequence (LCS) problem:Given two sequences X[1 . . m] and Y[1 . . n], finding a longest subsequence common to X and Y sequences both. It differs from the longest common substring problem,subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the different utility, and has applications in computational linguistics and bioinformatics.
Input Specification:
Input two sequences X[1 . . m] and Y[1 . . n] in two lines.
Output Specification:
the length of the LCS problem in the first line,the Longest common subsequence in the second line.There may be several subsequences of the same length,we choose the first sequence as the rows,the second sequence as the columns,and if the length of the downward and right paths is the same,we choose downward .
Input Example:
BDCABA ABCBDAB
Output Example:
4 BDAB
#include<bits/stdc++.h> using namespace std; #define MAX 50 char x[MAX],y[MAX]; int c[MAX][MAX],b[MAX][MAX]; void LCS(int i,int j){ if(i==0||j==0) return; if(b[i][j]==1){ LCS(i-1,j-1); cout<<x[i-1]; } else if(b[i][j]==2) LCS(i-1,j); else LCS(i,j-1); } int main(){ cin>>x>>y; int m,n; m=strlen(x); n=strlen(y); int i,j; for(i=1;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(x[i-1]==y[j-1]){ c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; b[i][j]=2; } else{ c[i][j]=c[i][j-1]; b[i][j]=3; } } } cout<<c[m][n]<<endl; LCS(m,n); return 0; }