Skip to content

Instantly share code, notes, and snippets.

@goakley
Created October 11, 2012 02:36
Show Gist options
  • Save goakley/3869838 to your computer and use it in GitHub Desktop.
Save goakley/3869838 to your computer and use it in GitHub Desktop.
FIND UNION
#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