# Poj Solution 1867

```http://poj.org/problem?id=1867

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

#define YES     { printf( "samen" );         continue; }
#define NO        { printf( "differentn" );    continue; }
#define PT(a)     (printf("an"));

struct node
{
vector< node* > next;
char c;

}mem[500];

char w[1000];
int u;

node* new_node()
{
mem[u++].next.clear();
return &mem[u-1];
}

int creat( int a, node *p )
{
node *q;
p->c = w[a];
a++;
if( w[a] == '(' )
{
a++;
while( 1 )//w[a] != '' )
{
if( w[a] == ',' ) a++;

q = new_node();
p -> next.push_back( q );
q -> next.push_back( p );
a = creat( a, q );

if( w[a] == ')' )
{
a++;
return a;
}
}
}
return a;
}

bool judge( node *p1, node *f1, node *p2, node *f2 )
{
int d1 = p1->next.size(), d2 = p2->next.size(), i, j, k;

if( d1 != d2 || p1->c != p2->c ) return false;

for( i = 0; i < d1; i++ )
if( p1->next[i] == f1 ) break;

for( j = 0; j < d2; j++ )
if( p2->next[j] == f2 ) break;

for( k = 1; k < d1; k++ )
if( ! judge( p1->next[(i+k)%d1], p1, p2->next[(j+k)%d2], p2 ) )
return false;

return true;
}

int main()
{
bool key;
int cas, i, j, h;

scanf( "%d", &cas );

while( cas-- )
{

u=0;

scanf( "%s", w );
mem[u].next.clear();
u++;
creat( 0, &mem[u-1] );

h = u;

scanf( "%s", w );
mem[u].next.clear();
u++;
creat( 0, &mem[u-1] );

if( u == 2 )
{
if( mem[0].c == mem[1].c )    YES
else NO
}

if( h*2 != u )
NO

for( i=0; i < h; i++ )
if( mem[i].next.size() == 1 )
break;

if( i < h )
{
for( key=1, j=h; j < u && key ; j++ )
if( mem[j].next.size() == 1 && mem[j].c == mem[i].c )
{
if( judge( mem[i].next[0], &mem[i], mem[j].next[0], &mem[j] ) )
{
key = 0;
}
}

if( !key ) YES
}

NO
}
return 0;
}

```
This entry was posted in poj. Bookmark the permalink.