-->
当前位置:首页 > 题库 > 正文内容

7-12 LCS (10 分)

Luz4年前 (2021-03-05)题库1300
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
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#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;
}


发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。