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

/***************************************************************************
New Alphabetical Order

Read in a new alphabetical order, and a list of words. Print out the words
in (the new) alphabetical order.
***************************************************************************/

#define MAX 80   /* maximum line length */
#define NUM 50   /* maximum number of words to alphabetize */
#define WORD 16  /* maximum word length */

void make_order(char line[MAX], int order[26]);
void sort(int order[26], char words[NUM][WORD+1], int count);
int compare(int order[26], char a[WORD+1], char b[WORD+1]);

/***************************************************************************
main
***************************************************************************/
void main(void)
{
char line[MAX];
char *ret;
char words[NUM][WORD+1];
int order[26];
int set = 0;
int count;

count = -1;
do {
	line[0] = 0;
	ret = gets(line);
	if (strlen(line) > 0)
		{
		/* This is either the new alphabetical order, or a word to be
		   alphabetized. */
		if (count == -1)
			/* This is the new alphabetical order. */
			make_order(line, order);
		else
			/* This is a word to be alphabetized. */
			strcpy(words[count], line);
		/* Either way, increment our counter. */
		count ++;
		}
	else if (count >= 0)
		{
		printf("Dataset %d\n", set+1);
		/* We should alphabetize the words and print them out in order. */
		sort(order, words, count);
		/* Reset our counters. */
		count = -1;
		set ++;
		printf("\n");
		}
	} while (ret);
}

/***************************************************************************
make_order

Makes an array such that given a letter c, the index of c in the new
alphabetical order is order[c - 'a'].
***************************************************************************/
void make_order(char line[MAX], int order[26])
{
int i;

for (i = 0; i < 26; i++)
	order[line[i] - 'a'] = i;
}

/***************************************************************************
sort

Print out the words in the new alphabetical order.
***************************************************************************/
void sort(int order[26], char words[NUM][WORD+1], int count)
{
int used[NUM];
int i, j;
int low;

/* Reset used array to all 0's. */
for (i = 0; i < count; i++)
	used[i] = 0;

for (i = 0; i < count; i++)
	{
	/* Each time through loop, find alphabetically-lowest unused word. */
	low = -1;
	for (j = 0; j < count; j++)
		if (!used[j])
			{
			if (low == -1)
				low = j;
			else
				if (compare(order, words[low], words[j]) == 1)
					low = j;
			}
	/* Now, low is index of smallest word. Print it out. */
	printf("%3d: %s\n", i, words[low]);
	/* Mark this word as used. */
	used[low] = 1;
	}
}

/***************************************************************************
compare

Compare the two words <a> and <b>. Return -1 if <a> is less, 0 if they are
the same, and 1 if <b> is less. Use the new alphabetical order defined by
<order>.
***************************************************************************/
int compare(int order[26], char a[WORD+1], char b[WORD+1])
{
int i = 0;
int aa, bb;

while (1)
	{
	if ((a[i] == 0) && (b[i] == 0))
		/* We have simultaneously hit the end of both words. They must be the
		   same. */
		return 0;
	if (a[i] == 0)
		/* We have hit end of a. It must be less. */
		return -1;
	if (b[i] == 0)
		/* We have hit end of b. It must be less. */
		return 1;
	/* Look up values of ith character in a and b in the new alphabet. */
	aa = order[a[i] - 'a'];
	bb = order[b[i] - 'a'];
	if (aa < bb)
		return -1;
	if (aa > bb)
		return 1;
	/* So far, words are same and haven't ended. Keep going. */
	i ++;
	}
}