lcs.txt

C精彩编程百例源码

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;


void longest_common_subsequence(string a,string b)
{
	int count,i,j,flag;
  
	//---------------获取两个要评估的字符串的长度--------------------------
	int m=a.length(),n=b.length(); 
	 /* cout<<m<<endl<<n<<endl;*/
	//----------------为存储中间结果的二维数组分配空间---------------
	  int **d=new int*[m+1];
	  for(int k=0;k<m+1;k++)
	  d[k]=new int[n+1];  

	  /*for(i=0;i<=m;i++)
		  for(j=0;j<=n;j++)
			  d[i][j]=1;
		  for(i=0;i<=m;i++)
		  for(j=0;j<=n;j++)
			  cout<<d[i][j]<<endl;*/


	  //-----------Clear the dynamic programming table-------------------------------
	  d[0][0]=0;
	  for(i=1;i<=m;d[i][0]=0,i++)
		  ;
	  for(j=1;j<=n;d[0][j]=0,j++)
		  ;

		  //---------------dynamic programming--------------------------
		  for(i=1;i<=m;i++)                     //for each pair of
		  {
			  for(j=1;j<=n;j++)                 //chars in string
			  {
				  if(a[i-1]==b[j-1])			//are they equal?
					  d[i][j]=d[i-1][j-1]+1;	// one more
				  else 
				  {  
					  if(d[i][j-1]>=d[i-1][j])  //or pick
					  d[i][j]=d[i][j-1];		//a smaller 
				  else d[i][j]=d[i-1][j-1];	   //neighbor
				  }
			  }
		  }
			/*	for(i=0;i<=m;i++)
		  for(j=0;j<=n;j++)
		   cout<<d[2][2]<<endl;
			  cout<<d[2][3]<<endl;*/

		//----------------display the subsequence----------------------
				  flag=count=d[m][n];
				  char *result=new char[count+1];
				  result[count]='\0';
				  for(i=m,j=n;(i!=0)&&(j!=0);)
				  {
					  if(d[i][j]==d[i-1][j])
						  i--;
					  else if(d[i][j]==d[i][j-1])
						  j--;
					  else {
						  result[--count]=a[i-1];
						  i--,j--;
					  }
				  }
			for(i=0;i<flag;i++)
				cout<<result[i];
			cout<<endl;
			//
            
	  //-----------释放内存------------
          //delete result;
		  
			for(i=0;i<=m;i++)
			  delete[] d[i];
		 delete[] d;
		 
		delete [] result;
}
int main(int argc, char* argv[])
{
	string a="abcd",b="xbadz";
	
longest_common_subsequence(a,b);
return 0;
}