?? 1325.cpp
字號:
/* 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;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -