Created
October 11, 2012 02:36
-
-
Save goakley/3869838 to your computer and use it in GitHub Desktop.
FIND UNION
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <errno.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#ifndef ENOMEM | |
#define ENOMEM 12 | |
#endif | |
/*****************************************************************************/ | |
/*** TRIE ***/ | |
/** Structures **/ | |
/* A node of a trie */ | |
typedef struct trie_node { | |
struct trie_node* branches[26]; | |
short subnode_count; | |
short is_value; | |
} trie_node; | |
/* Creates a new trie_node pointer */ | |
trie_node* trie_node_malloc() { | |
trie_node *result = malloc(sizeof(trie_node)); | |
if (!result) return NULL; | |
int i; | |
for (i = 0; i < 26; i++) | |
result->branches[i] = NULL; | |
result->subnode_count = 0; | |
result->is_value = 0; | |
return result; | |
} | |
/* Frees a trie_node pointer, INCLUDING ITS CHILDREN */ | |
trie_node* trie_node_free(trie_node *val) { | |
if (!val) | |
return NULL; | |
int n = 0; | |
for ( ; n < 26; n++) { | |
trie_node_free(val->branches[n]); | |
val->branches[n] = NULL; | |
} | |
val->subnode_count = 0; | |
val->is_value = 0; | |
free(val); | |
return val; | |
} | |
/** Functions **/ | |
/* Add a string to a trie. The string to be added is the substring of the | |
* 'str' argument, the first character being str[start] and the last being | |
* str[end-1]. | |
* Returns 1 on successful add. Upon failure, returns 0, and: | |
* - If the string is already in the trie, nothing happens | |
* - If there is no room to store the string, 'errno' will be set to ENOMEM | |
* - If an invalid character is encountered, 'errno' will be set to EDOM */ | |
char trie_node_add(trie_node *trie, char* str, int start, int end) { | |
/* base case */ | |
if (start == end) { | |
if (trie->is_value) | |
return 0; | |
return (trie->is_value = 1); | |
} | |
/* extract the character value to the [0,25] alphabet range */ | |
int charval = (str[start]<97 ? str[start]+32 : str[start])-97; | |
if (charval < 0 || charval > 25) { | |
errno = EDOM; | |
return 0; | |
} | |
/* recurse with the next branch */ | |
if (!(trie->branches[charval])) { | |
trie->branches[charval] = trie_node_malloc(); | |
if (!(trie->branches[charval])) { | |
errno = ENOMEM; | |
return 0; | |
} | |
} | |
int add = trie_node_add(trie->branches[charval], str, start+1, end); | |
/* handle the result of the recursive add */ | |
if (!add) | |
return 0; | |
trie->subnode_count++; | |
return 1; | |
} | |
/* Determines if a string is contained by a trie. The search string is the | |
* substring of the 'str' argument, the first character being | |
* str[start] and the last being str[end-1]. | |
* Returns 1 if the string is found. Otherwise, returns 0, and if an invalid | |
* character is encountered in the string, sets errno to EDOM. | |
*/ | |
char trie_node_contains(trie_node *trie, char* str, int start, int end) { | |
if (start < 0) start = 0; | |
if (end < 0) end = 0; | |
int n = start; | |
for ( ; n < end; n++) { | |
int charval = (str[n]<97?str[n]+32:str[n])-97; | |
if (charval < 0 || charval > 25) { | |
errno = EDOM; | |
return 0; | |
} | |
if (!(trie = trie->branches[charval])) | |
return 0; | |
} | |
return trie->is_value; | |
} | |
/* Convert a trie to a lexographically sorted array. | |
* Returns the number of elements added to the array. If 'start' is greater | |
* than the size of the array, errno is set to EDOM. */ | |
int trie_node_array(trie_node *trie, char* *array, | |
int start, int end, char *prefix) { | |
/* error checking */ | |
if (!array || !trie) | |
return 0; | |
if (start >= end) { | |
errno = EDOM; | |
return 0; | |
} | |
int prefix_len = strlen(prefix); | |
int count = 0; | |
/* add this value to the array if necessary */ | |
if (trie->is_value) { | |
array[start] = malloc(sizeof(char)*(prefix_len+1)); | |
if (!array[start]) { | |
errno = ENOMEM; | |
return 0; | |
} | |
strcpy(array[start], prefix); | |
count++; | |
if (start+count == end) | |
return count; | |
} | |
/* create a new prefix string */ | |
char *prefix_string = malloc(sizeof(char)*(prefix_len+2)); | |
if (!prefix_string) { | |
errno = ENOMEM; | |
return count; | |
} | |
/* copy the old prefix into the new one */ | |
strcpy(prefix_string, prefix); | |
/* put the terminating null character at the end of the array */ | |
prefix_string[prefix_len+1] = 0; | |
/* recurse over the branches */ | |
int i = 0; | |
for ( ; i < 26; i++) { | |
prefix_string[prefix_len] = i+97; | |
int result = trie_node_array(trie->branches[i], array, start+count, end, | |
prefix_string); | |
count += result; | |
if (start+count == end) | |
break; | |
} | |
free(prefix_string); | |
return count; | |
} | |
/*** /TRIE ***/ | |
/*****************************************************************************/ | |
int main() { | |
trie_node *trie = trie_node_malloc(); | |
if (!trie) { | |
fprintf(stderr, "Out of memory\n"); | |
return 1; | |
} | |
int N; | |
if (!(scanf("%d", &N))) | |
return 1; | |
int n = 0; | |
char *strin = malloc(sizeof(char)*2001); | |
for ( ; n < N; n++) { | |
printf("Substringing element %d\n", n); | |
if (!(scanf("%s", strin))) | |
return 1; | |
int len = strlen(strin); | |
int c = 0; | |
for ( ; c < len; c++) { | |
int d = 0; | |
for ( ; d < len-c; d++) { | |
trie_node_add(trie, strin, d, d+c+1); | |
} | |
} | |
} | |
free(strin); | |
char* *array = malloc(sizeof(char*)*(trie->subnode_count)); | |
trie_node_array(trie, array, 0, trie->subnode_count, ""); | |
int Q; | |
if (!scanf("%d", &Q)) | |
return 1; | |
int q = 0; | |
for ( ; q < Q; q++) { | |
int in = 0; | |
if (!scanf("%d", &in)) | |
return 1; | |
if (in > trie->subnode_count) | |
printf("INVALID\n"); | |
else | |
printf("%s\n", array[in-1]); | |
} | |
int i = 0; | |
for ( ; i < trie->subnode_count; i++) | |
free(array[i]); | |
free(array); | |
trie_node_free(trie); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment