1292.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1292 on 2006-04-25 at 17:03:52 */ 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int DFN = 3200;

bool same(char*, int, char*, int);
void parse(vector<int>&, char*, int);

int main()
{
	int t, T;
	char sq[2][DFN];

	scanf("%d\n", &T);
	for(t = 0; t < T; t++) {
		sq[0][0] = sq[1][0] = '0'; gets(sq[0]+1); gets(sq[1]+1);
		printf("%s\n", same(sq[0], strlen(sq[0])+1, sq[1], strlen(sq[1])+1) ? "same" : "different");
	}
	
	return 0;
}

bool same(char* dfa, int la, char* dfb, int lb)
{
	if(la != lb) return false;
	else if(!strncmp(dfa, dfb, la)) return true;
	else {
		vector<int> sa, sb;
		la -= 2; lb -= 2; dfa++; dfb++;
		parse(sa, dfa, la); parse(sb, dfb, lb);
		if(sa.size() != sa.size()) return false;
		int i, j, n = sa.size()-1;
		vector<bool> use(n, false);
		for(i = 0; i < n; i++) {
			for(j = 0; j < n; j++)
				if(!use[j] && same(dfa+sa[i], sa[i+1]-sa[i], dfb+sb[j], sb[j+1]-sb[j]))
					{ use[j] = true; break; }
			if(j == n) return false;
		}
		return true;
	}
}
void parse(vector<int>& vi, char* b, int l)
{
	vi.clear();
	int i, zo = 0;
	for(i = 0; i < l; i++) {
		if(zo == 0) vi.push_back(i);
		if(b[i] == '0') zo++;
		else zo--;
	}
	vi.push_back(i);
}