1325.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1325 on 2006-03-11 at 11:01:54 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 26;

class Word {
public:
	char *str;
	int len;
	bool operator <(const Word&) const;
};
bool Word::operator <(const Word& w) const {
	return strcmp(str, w.str) > 0;
}

int code[MAX], test[MAX], cn, wn;
bool used[MAX];
Word w[64];

class Trie {
public:
	static Trie* root;
	int floor, len;
	Trie *child[MAX];
	Trie(int);
	void insert(const char*, const int);
	void find(int) const;
};
Trie* Trie::root = new Trie(0);
Trie::Trie(int k) : floor(k), len(0) {
	int i;
	for(i = 0; i < MAX; i++) child[i] = NULL;
}
void Trie::insert(const char* str, const int l) {
	len |= 1 << l;
	if(str[floor] == 0) return;
	if(child[str[floor]-'A'] == NULL) child[str[floor]-'A'] = new Trie(floor+1);
	child[str[floor]-'A']->insert(str, l);
}
void Trie::find(int fn) const {
	int i;
	if(fn == wn) {
		for(i = 0; i < MAX; i++) 
			if(test[i] != -1) code[test[i]] = i;
		cn++;
	} else if(len & (1 << w[fn].len)) {
		char bit = w[fn].str[floor];
		if(bit == 0) Trie::root->find(fn+1);
		else if(test[bit-'A'] == -1) {
			for(i = 0; i < MAX; i++)
				if(child[i] != NULL && !used[i]) {
					used[i] = true; test[bit-'A'] = i; 
					child[i]->find(fn);
					used[i] = false; test[bit-'A'] = -1;
					if(cn > 1) return;
				}
		} else {
			if(child[test[bit-'A']] == NULL) return;
			child[test[bit-'A']]->find(fn);
			if(cn > 1) return;
		}
	}
}

int main()
{
	int n, i, j, t, T;
	char word[10][128];

	scanf("%d\n", &n);
	for(i = 0; i < n; i++) {
		gets(word[0]);
		Trie::root->insert(word[0], strlen(word[0]));
	}
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		memset(test, -1, sizeof(test)); memset(code, -1, sizeof(code)); 
		memset(used, false, sizeof(used));
		int m = wn = cn = 0;
		scanf("\n");
		for(j = 0; gets(word[j]) != NULL && word[j][0] != 0; j++) {
			bool begin = false;
			for(i = 0; word[j][i] != 0; i++)
				if(word[j][i] == ' ') { begin = false; word[j][i] = 0; }
				else if(!begin) { begin = true; w[m++].str = word[j] + i; }
		}
		sort(w, w+m);
		for(i = 0; i < m; i++) {
			w[i].len = strlen(w[i].str);
			if(i == 0 || strcmp(w[i].str, w[i-1].str)) w[wn++] = w[i];
		}
		Trie::root->find(0);
		if(cn == 0) printf("#No solution#");
		else if(cn > 1) printf("#More than one solution#");
		else for(i = 0; i < MAX; i++) putchar((code[i] < 0) ? '*' : code[i]+'A');
		putchar('\n');
	}

	return 0;
}