最长公共子川.txt

里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等

#include< iostream>
#include <string>
using namespace std ;
const N = 100 ;
int l[N][N] ;

int LCS_Length(char a[],char b[],int m,int n )
{

	int i,j ;
	for( i = 0 ; i < m ; i ++) l[i][0]  = 0;
	for( j = 0 ; j < n ; j ++) l[0][j]  = 0;

	for( i = 1 ; i <= m ; i ++)
		for(j = 1 ; j <= n ; j ++)
		{
			if( a[i-1] == b[j-1] ) 
				l[i][j] = l[i-1][j-1] + 1 ;
			else
			{
				l[i][j] = l[i-1][j] >= l[i][j-1] ? l[i-1][j] : l[i][j-1];
			}
		}

	for( i = 0 ; i < m ; i ++)
	{
		for(j = 0 ; j < n ; j ++)
			cout << l[i][j] << " ";
		cout << endl;
	}
	return l[m][n] ;
}

char* LCS(char  s[],char  a[], char b[],int m,int n)   
 { 
    int  k;  
    k=LCS_Length(a,b,m,n);   cout<<k<<endl;
    s[k]='\0';   
    while (k>0)  
	{
       if   (l[m][n]==l[m-1][n]) m--;   
       else if   (l[m][n]==l[m][n-1]) n--;   
       else { s[--k]=a[m-1] ;   m--; n--; }  
	}   
    return   s;   
 }   

int main()
{
	char a[N],b[N],s[N] ;
	int m,n ;
	cin>>a>>b ;
	m = strlen( a ) ;
	n = strlen( b ) ;
//	cout<<LCS_Length(a,b,m,n,l) <<endl;
	cout<<LCS(s,a,b,m,n)<<endl ;
	return 1;
}