1934.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <set>
using namespace std;

int ans[81][81];
int from[81][81];
char route1[100],route2[100];
int n,m;

void doit()
{
	int i,j;
	for( i=0; i<=n; i++)
		ans[i][0] = 0;
	for( j=0; j<=m; j++)
		ans[0][j] = 0;

	for( i=1; i<=n; i++ )
	for( j=1; j<=m; j++ )
	{
		if( route1[i] == route2[j] )
		{
			ans[i][j] = ans[i-1][j-1] + 1;
			from[i][j] = 1;
		}
		else ans[i][j] = -1;

		if( ans[i-1][j] == ans[i][j] )
			from[i][j] |= 2;
		else if( ans[i-1][j] > ans[i][j] )
			from[i][j] = 2, ans[i][j] = ans[i-1][j];

		if( ans[i][j-1] == ans[i][j] )
			from[i][j] |= 4;
		else if( ans[i][j-1] > ans[i][j] )
			from[i][j] = 4, ans[i][j] = ans[i][j-1];
	}
}



struct cmp
{
	bool operator()(vector<char>* a,vector<char>* b)const
	{
		return std::lexicographical_compare( a->begin(), a->end(), b->begin(), b->end() );
	}
};

set< vector<char>*, cmp > word[81][81],output;

vector<char> w;

void search(int a,int b,int r)
{
	
	if( word[a][b].find( &w ) == word[a][b].end() )
	{
		vector<char>* p = new vector<char>( w );
		word[a][b].insert( p );
	}
	else return;

	if( r < 0 )
	{
		if( output.find( &w ) == output.end() )
		{
			vector<char>* p = new vector<char>( w );
			output.insert( p );
		}
		return;
	}

	if( from[a][b] & 1 )
	{
		w[r] = route1[a];
		search( a-1, b-1, r-1);
		w[r] = '\0';
	}

	if( from[a][b] & 2 )
		search( a-1, b, r );

	if( from[a][b] & 4 )
		search( a, b-1, r );
}

int main()
{
	int i,j;

	scanf("%s %s",route1+1,route2+1);

	n = strlen( route1+1 );
	m = strlen( route2+1 );

	doit();

	for(i=0;i<n;i++)
	for(j=0;j<m;j++)
		word[i][j].clear();

	w.resize(ans[n][m],'\0');

	search( n, m, ans[n][m]-1 );

	set< vector<char>*, cmp >::iterator iter, iter2;

	for( iter=output.begin(), i=0; iter != output.end() ; iter++,i++ )
	{
		if( !i || cmp()( *iter2, *iter ) )
		{	
			for(j=0;j<ans[n][m];j++)
				printf("%c",(*(*iter))[j] );
			printf("\n");
		}
		iter2 = iter;
	}

	return 0;
	
}