最长公共子序列.cpp

动态规划算法中的最长公共子序列算法

#include <iostream.h>
#include "make2DArray.h"
#include "string.h"
#include "fstream.h"
#include "stdlib.h"
#define N 100

int LCSLength(int i,int j,char x[],char y[],int **c,int **kay)
{
	if(c[i][j]>0)
		return c[i][j];
	if(i==0||j==0){
		c[i][j]=0;
	return 0;
	}
	if(x[i]==y[j]){
		kay[i][j]=0;
		LCSLength(i-1,j-1,x,y,c,kay);
		c[i][j]=c[i-1][j-1]+1;
		return c[i][j];
	}
	int u=LCSLength(i-1,j,x,y,c,kay);
	int v=LCSLength(i,j-1,x,y,c,kay);
	if(u>v){
		kay[i][j]=1;
		c[i][j]=u;
	}else{
		kay[i][j]=2;
		c[i][j]=v;
	}
	return c[i][j];
}

void LCS(int i,int j,char *x,int **b)
{
	if(i==0||j==0)
		return;
	if(b[i][j]==0)
	{
		LCS(i-1,j-1,x,b);
		cout<<x[i];
	}
	else if(b[i][j]==1)
		LCS(i-1,j,x,b);
	else
		LCS(i,j-1,x,b);
}

/*void main(void)
{
	char a[]="1abcdefghijk",b[]="0abcdjki";
	int **kay,**cc;
	int m=strlen(a);
	int n=strlen(b);
	make2DArray(cc,m+1,n+1);
	make2DArray(kay,m+1,n+1);
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j++)
			cc[i][j]=0;
		LCSLength(m,n,a,b,cc,kay);
		LCS(m,n,a,kay);
		cout<<endl;
		delete kay;
		delete cc;
}

void main(void)
{
	
	char string1[]="abcdefghi",string2[]="abcd";
	int p=0;
	int q=0;
	ofstream my_file("sample.txt");
	if(!my_file){
		cerr<<"error open file!";
		exit(0);
	}
	
	while(string1[p])
		my_file.put(string1[p++]);

	while(string2[q])
		my_file.put(string2[q++]);
	my_file.close();
		

	int **kay,**cc;
  	int m=p;
	int n=q;
	make2DArray(cc,m+1,n+1);
	make2DArray(kay,m+1,n+1);
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j++)
			cc[i][j]=0;
		LCSLength(m,n,string1,string2,cc,kay);
		LCS(m,n,string1,kay);
		cout<<endl;
		delete kay;
		delete cc;
}*/

void main()
{
	ifstream ifs("abc.txt");
	if(!ifs){
		cerr<<"error open file!";
		exit(0);
	}

	char a[50],b[50] ;
	
	ifstream input("abc.txt");
	for(int k=0;k<12;k++)
	{
		input>>a[k];
	}
	a[k]='\0';
	cout<<a;
	cout<<endl;

	for(int j=0;j<13;j++)
	{
		input>>b[j];
	}
	b[j]='\0';
	cout<<b;
	cout<<endl;
    
	int **kay,**cc;
  	int m=strlen(a);
	int n=strlen(b);
	make2DArray(cc,m+1,n+1);
	make2DArray(kay,m+1,n+1);
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j++)
			cc[i][j]=0;
		LCSLength(m,n,a,b,cc,kay);
		LCS(m,n,a,kay);
		cout<<endl;
		delete kay;
		delete cc;
}