1004 anagrams by stack.cpp

zoj 1004 的题目

#include<iostream>
#include<cstring>
using namespace std;

char a[ 1000 ], b[ 1000 ];
int len;

int curOut, curTest;
char step[ 2005 ], curOutput[ 1000 ];

//==============stack==================
int top;
char stack[ 1000 ];
void push( char ele ) {	stack[ ++ top ] = ele;	}
char pop()	{	return stack[ top -- ];	}
bool isEmpty()	{	return top == -1;	}
//==============stack==================

void init()
{
	len = strlen( a );
	curOut = curTest = 0;
	top = -1;
}

int dicU1[ 26 ], dicL1[ 26 ];
int dicU2[ 26 ], dicL2[ 26 ];

bool basicCheck()
{
	len = strlen( a );

	if ( len != strlen( b ) )
		return false;
	
	memset( dicU1, 0, sizeof( dicU1 ) );
	memset( dicL1, 0, sizeof( dicL1 ) );

	memset( dicU2, 0, sizeof( dicU2 ) );
	memset( dicL2, 0, sizeof( dicL2 ) );

	int i;
	for ( i = 0; i < len; i ++ )
	{
		if ( a[ i ] >= 'a' && a[ i ] <= 'z' )
			dicL1[ a[ i ] - 'a' ] ++;
		else
			dicU1[ a[ i ] - 'A' ] ++;

		if ( a[ i ] >= 'a' && a[ i ] <= 'z' )
			dicL2[ b[ i ] - 'a' ] ++;
		else
			dicU2[ b[ i ] - 'A' ] ++;
	}

	for ( i = 0; i < 26; i ++ )
		if ( dicL1[ i ] != dicL2[ i ] || dicU1[ i ] != dicU2[ i ] )
			return false;

	return true;
}

void dfs( int i )
{
	if ( i == len * 2 )
	{
		for ( int j = 0; j < 2 * len; j ++ )
			printf( "%c ", step[ j ] );
		putchar( '\n' );

		return;
	}

	if ( curTest < len )
	{
		push( a[ curTest ] );
		curTest ++;
		step[ i ] = 'i';
		dfs( i + 1 );
		curTest --;
		pop();
	}

	if ( !isEmpty() )
	{
		curOutput[ curOut ] = pop();
		if ( curOutput[ curOut ] == b[ curOut ] )
		{
			curOut ++;
			step[ i ] = 'o';
			dfs( i + 1 );
			curOut --;
		}
		push( curOutput[ curOut ] );
	}
}

int main()
{
	while ( scanf( "%s", a ) != EOF )
	{
		scanf( "%s", b );
		init();
		if ( !basicCheck() )
		{
			printf( "[\n]\n" );
			continue;
		}
		printf( "[\n" );
		dfs( 0 );
		printf( "]\n" );
	}

	return 0;
}