1307.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1307 on 2005-10-03 at 12:54:08 */ 
#include <cstdio>
#include <cstring>
#define  MAX  5000

class BSTreeNode {
public:
	char content[128];
	long number;
	BSTreeNode *left;
	BSTreeNode *right;
	void init(char *s) {
		left = NULL;
		right = NULL;
		number = 1;
		strcpy(content, s);
	}
	long add(BSTreeNode *node) {
		BSTreeNode *p = this;
		int i;
        while(true) {
            i = strcmp(node->content, p->content);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    p->left = node;
                    return node->number;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    p->right = node;
                    return node->number;
                }
            } else {
                p->number++;
				return p->number;
            }
        }
	}
	void leftRootRight(const long max) {
		if(left != NULL) {
			left->leftRootRight(max);
		}
		if(number == max) {
			printf("%s\n", content);
		}
		if(right != NULL) {
			right->leftRootRight(max);
		}
	}
};

char* slwr(char *);

int main()
{
	char word[128];
	long max = -1, n;
	int i, nodeN = 0;
	BSTreeNode *Node[MAX], *root = NULL;
	
	for(i = 0; i < MAX; i++) {
		Node[i] = new BSTreeNode;
	}
	while(scanf("%[a-zA-Z0-9]", word) != EOF) {
		slwr(word);
		Node[nodeN]->init(word);
		if(root == NULL) {
			root = Node[nodeN];
			nodeN++;
		} else {
			n = root->add(Node[nodeN]);
			if(n == 1) {
				nodeN++;
			}
			if(n > max) {
				max = n;
			}
		}
		scanf("%*[^a-zA-Z0-9]");
	}
	printf("%ld occurrences\n", max);
	root->leftRootRight(max);
	
	return 0;
}

char* slwr(char *s)
{
	int i;
	for(i = 0; ; i++) {
		if(s[i] >= 'A' && s[i] <= 'Z') {
			s[i] = s[i] - 'A' + 'a';
		} else if(s[i] == 0) {
			break;
		}
	}
	
	return s;
}