1530.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1530 on 2006-02-21 at 19:35:41 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAX = 26;

char top[32], end[32], line[3200][32];
int ln = 0;

class Trie {
public:
	static Trie *root;
	int floor, n;
	Trie *child[MAX];
	Trie(int, Trie*);
	void insert(const char*);
	void travel();
	void find(const Trie*) const;
};
Trie* Trie::root = new Trie(0, NULL);
Trie::Trie(int k, Trie* p) : floor(k), n(0) {
	int i;
	for(i = 0; i < MAX; i++)	child[i] = NULL;
}
void Trie::insert(const char* word) {
	int k = word[floor];
	if(k == 0) { n++; return; }
	else if(child[k-'a'] == NULL) child[k-'a'] = new Trie(floor+1, this);
	child[k-'a']->insert(word);
}
void Trie::travel() {
	int i;
	for(i = 0; i < MAX; i++) {
		if(child[i] == NULL) continue;
		top[floor] = i + 'a'; child[i]->travel();
	}
	if(n != 0) { top[floor] = 0; find(root); }
}
void Trie::find(const Trie* a) const {
	int i;
	if(a->n != 0 && n != 0) { end[a->floor] = 0; sprintf(line[ln++], "%s%s", top, end); }
	for(i = 0; i < MAX; i++) {
		if(a->child[i] == NULL || child[i] == NULL) continue;
		end[a->floor] = i + 'a'; child[i]->find(a->child[i]);
	}
}

int cmp(const void* a, const void* b) { return strcmp((char*)a, (char*)b); }

int main()
{
	char word[32];
	int i;

	while(gets(word) != NULL) Trie::root->insert(word);
	Trie::root->travel();
	qsort(line, ln, sizeof(line[0]), cmp);
	for(i = 0; i < ln; i++)
		if(i == 0 || strcmp(line[i], line[i-1])) puts(line[i]);

	return 0;
}