#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ttree_tag {
	int have_word;
	int have_next;
	struct ttree_tag *next[26];
} ttree_node;

int alphabet_to_int(char c) {
	if ('a' <= c && c <= 'z') return c - 'a';
	//if ('A' <= c && c <= 'z') return c - 'A' + 26;
	return -1;
}

char int_to_alphabet(int i) {
	if (0 <= i && i < 26) return 'a' + i;
	return -1;
}

ttree_node* add_ttree(ttree_node *node, char *c) {
	ttree_node* next_node;
	
	if (node == NULL) {
		node = (ttree_node*)malloc(sizeof(ttree_node));
		node->have_word = 0;
		node->have_next = 1;
		memset(node->next, NULL, sizeof(ttree_node*) * 26);
	}

	if (*c == '\0') {
		node->have_word = 1;
		return node;
	}

	next_node = node->next[alphabet_to_int(*c)];
	next_node = add_ttree(next_node, c + 1);
	node->next[alphabet_to_int(*c)] = next_node;
	return node;
}


void print_ttree(ttree_node* node, char *buf, int n) {

	if (node->have_word == 1) {
		int i;
		for (i = 0; i < n; i++) printf("%c", buf[i]);
		printf("\n");
	}

	if (node->have_next == 1) {
		int i;
		for (i = 0; i < 26; i++) {
			if (node->next[i] != NULL) {
				buf[n] = int_to_alphabet(i);
				print_ttree(node->next[i], buf, n + 1);
			}
		}
		return;
	}

	abort();
}

int main()
{
	ttree_node *root = NULL;
	FILE *fp;
	char buf[128];
	int i;

	fp = fopen("data.txt", "r");
	if (fp == NULL) {
		exit(-1);
	}

	while(NULL != fgets(buf, 128, fp)) {
		/* 改行文字の除去 */
		for (i = 0; i < 128; i++) {
			if (buf[i] == '\n') {
				buf[i] = '\0';
				break;
			}
		}

		root = add_ttree(root, buf);
	}

	print_ttree(root, buf, 0);

	return 0;
}