Perfect Hash Contest Problem.

PerfectHash.c

#include <stdio.h>

#define LIST_MAX_SIZE 200
#define NUMBER_OF_WORDS 30
#define NUMBER_OF_CHARACTERS 5

typedef struct {
	char word[NUMBER_OF_CHARACTERS];
	int number;
	int hashedNumber;
} WordStructure;
/*
 * Insertion sort sorts the list of words from the smallest number representation of a word to the largest one.
 * Each element of the list is a structure.
 * Each word (structure) has a representation of:
 * 	- Characters
 *	- Number (Left Shift by 5)
 *	- HashedNumber
 */
void insertionSort(WordStructure numbers[], const int array_size) {
	int i, j;
	WordStructure temp;

	for (i = 1; i < array_size; i++) {
		temp = numbers[i];
		j = i;
		while ((j > 0) && (numbers[j - 1].number > temp.number)) {
			numbers[j] = numbers[j - 1];
			j = j - 1;
		}
		numbers[j] = temp;
	}
}
/*
 * Hash function suggested by the problem description.
 */
int hashFunction(int C, int wordNumber, int n) {
	return (C / wordNumber) % n;
}

int main() {
	int n = 0, i , j , k , len , buffer, isMultipleOf;
	unsigned long long C, pow;
	char setofWords[LIST_MAX_SIZE];
	char delims[] = " ", *result = NULL;
	WordStructure words[NUMBER_OF_WORDS];
	
	gets(setofWords);
	while (strlen(setofWords) > 0) {
		printf("\n%s\n", setofWords);
		/*
		 * Begin:	Tokenizing the set of words entered from the keyboard.
		 */
		result = (char*) strtok( setofWords, delims );
		n = 0;
		while( result != NULL ) {
	      	strcpy( words[n].word, result );
			result = ( char* ) strtok( NULL, delims );
			n++;
	  	}
		/*
		 * End:		Tokenizing the set of words entered from the keyboard.
		 */
		/*
		 * Begin:	Calculating the Left Shift by 5 of each word and storing it.
		 */
		for ( i = 0 ; i < n ; i++ ) {
			len = strlen(words[i].word);
			buffer = 0;
			for ( j = len - 1; j >= 0; j -- ) {
				if (len - j > 1) {
					pow = 1;
					for (k = len - j; k > 1; k--) {
						pow *= 32;
					}
					buffer += pow * (words[i].word[j] - 96);
				} else {
					buffer += words[i].word[j] - 96;
				}
			}
			words[i].number = buffer;
		}
		/*
		 * End:		Calculating the Left Shift by 5 of each word and storing it.
		 */
		/*
		 * Sorting words according to the counted number above.
		 */
		insertionSort(words, n);
		/*
		 * Begin:	Hashing the list of words, word by word.
		 *			This operation computes the hashing of each word.
		 *			If the hashing function yields similar values for different
		 *			words, we take advantage of another formula to get the result:
		 *		 		- Wi = ((C / words[i].number) + 1) * words[i].number
		 *		 		- Wj = ((C / words[j].number) + 1) * words[j].number
		 *			Meanwhile, the loop is restarting from scratch.
		 *
		 *			Worst case: W(n) >= n²
		 */
		C = words[0].number;
		for ( i = 0 ; i < n; i++ ) {
			unsigned long long Wi, Wj;
			words[i].hashedNumber = hashFunction(C, words[i].number, n);
			Wi = ((C / words[i].number) + 1) * words[i].number;
			for ( j = 0 ; j < n ; j ++ ) {
				if ( i != j ) {
					words[j].hashedNumber = hashFunction(C, words[j].number, n);
					if ( words[i].hashedNumber == words[j].hashedNumber ) {
						Wj = ((C / words[j].number) + 1) * words[j].number;
						if ( Wi <= Wj) {
							C = Wi;
						} else {
							C = Wj;
						}
						i = 0;
						break;
					}
					
				}
			}
		}
		printf("%d\n", C);
		gets(setofWords);
	}
	printf("\n");
	return 0;
}