#include<iostream>

using namespace std;

const int MAXN = 508 ;

__int64 a[MAXN] , b[MAXN] ;
__int64  count[MAXN][MAXN] = { 0 };
char map[MAXN][MAXN] ;
int n1 , n2 ;

void solve( void )
{
	int i , j ;
	for( i = 1; i < MAXN ;i ++ )
		count[i][0] = count[0][i] = 0 ;
	for( i = 1 ; i <= n1 ; i ++ )
		for( j = 1; j <= n2 ;j ++ )
		{
			if( a[i] == b[j] )
			{
				count[i][j] = count[i - 1][j - 1] + 1 ;
				map[i][j]   = '\\';
			}
			else if( count[i - 1][j] >= count[i][j - 1] )
			{
				count[i][j] = count[i - 1][j] ;
				map[i][j] ='|' ;
			}
			else 
			{
				count[i][j] = count[i][ j - 1] ;
				map[i][j] = '-';
			}
		}
	return ;
}

void LST ( int x , int y )
{
	if( x == 0 || y == 0 ) return ;
	if( map[x][y] == '\\' )
	{
		LST( x - 1 , y - 1 );
		//cout << a[x] <<' ' ;
		printf("%I64d ",a[x] ) ;
	}
	else if( map[x][y] == '|' )
		LST( x - 1 ,  y ) ;
	else LST( x , y - 1 ) ;
	return ;
}


int main( void )
{
	int i  ;
	//cin >> n1 ;
	scanf("%d",&n1 ) ;
	for( i = 1 ;i <= n1 ; i ++ )
	//	cin >> a[i] ;
	    scanf("%I64d",&a[i] ) ;
//	cin >> n2 ;
	scanf("%d",&n2 ) ;
	for( i = 1 ;i <= n2 ; i ++ )
	//	cin >> b[i] ;
	    scanf("%I64d",&b[i] ) ;
	solve() ;
//	cout << count[n1][n2] << endl ;
	printf("%d\n",count[n1][n2] ) ;
	LST( n1 , n2 );
	//cout << endl ;
	printf("\n") ;
	return 0 ;
}
	

• 那是求最长公共子串的，不是最长升序公共子串 (1527) windbells 2004-12-03 22:50:07
  • 高手~~~~一语点醒~~~~~~~~~我对你的崇拜有如淘淘江水~~~~~~~~~~~ (0) Juwend 2009-07-12 11:26:21