Find Strings hacker rank solution in c language | | C- language


Find Strings hacker rank solution in c language | | C- language

Questions

You are given n strings w1, w2, ......, wn. Let Si denote the set of strings formed by considering all unique substrings of the string wi. A substring is defined as a contiguous sequence of one or more characters in the string. More information on substrings can be found here. Let S = {S1 U S2 U .... Sn} .i.e S is a set of strings formed by considering all the unique strings in all sets S1, S2, ..... Sn. You will be given many queries, and for each query, you will be given an integer 'k'. Your task is to display the lexicographically kth smallest string from the set S.
Input Format


The first line of input contains a single integer n, denoting the number of strings. Each of the next n lines consists of a string. The string on the ith line (1<=i<=n) is denoted by wi and has a length mi. The next line consists of a single integer q, denoting the number of queries. Each of the next q lines consists of a single integer k.
Note: The input strings consist only of lowercase english alphabets 'a' - 'z'.
Constraints
1<= n <=50
1<= mi <=2000
1<= q <=500
1<= k <=1000000000
Output Format
Output q lines, where the ith line consists of a string which is the answer to the ith query. If the input is invalid (i.e., k> size of S), display "INVALID" for that case.

Answer:

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

char input[3000], output[3000];
int queries[600];
int malloc_cnt = 0;

//HASH table for ints implementation
typedef struct bucket_item{

int key;
char *val;
struct bucket_item *next;
} HASH_NODE;

#define HASH_MODULUS 997
HASH_NODE* hash_arr[HASH_MODULUS];

int calc_hash(int i) {
return (i % HASH_MODULUS);
}
HASH_NODE *get_hash_table_entry(int i) {
int hash = calc_hash(i);
HASH_NODE *item = hash_arr[hash];
if(item == NULL) { return NULL; }
while(item) {
if(item->key == i) { return item; }
item = item->next;
}
return NULL;
}
void insert_into_hash_table(int i) {
if(get_hash_table_entry(i) != NULL) { return; }
int hash = calc_hash(i);
HASH_NODE *new_node = malloc(sizeof(HASH_NODE)); 
new_node->key = i;
new_node->val = malloc(sizeof(char) * 2200);
new_node->next = NULL;
strcpy(new_node->val, "INVALID");
if(hash_arr[hash] == NULL) { 
hash_arr[hash] = new_node;
} else {
new_node->next = hash_arr[hash];
hash_arr[hash] = new_node;
}
}
void print_keys_in_hash_table() {
int i;
HASH_NODE *tmp;
printf("HASH TABLE ENTRIES\n");
for(i = 0; i < HASH_MODULUS; i++) {
tmp = hash_arr[i];
while(tmp) {
printf("%d\n", tmp->key);
tmp = tmp->next;
}
}
printf("HASH TABLE ENTRIES OVER\n");
}
//

typedef struct node{
char *word;
int len;
struct node *children[26];
}NODE;

typedef void (*TRAVERSE_FUNC) (char *, int);

NODE* tree_root;

//return the length of the largest common prefix of str1, str2
int prefix_match_cnt(char * str1, char *str2, int len1, int len2) {
int i = 0;
while((i < len1) && (i < len2) && (*str1++ == *str2++)) {
i++;
}
return i;
}

NODE* create_node(char *str, int len) {
int i;
NODE *tmp = malloc(sizeof(NODE));
tmp->word = str;
tmp->len = len;
for(i = 0; i < 26; i++) {
tmp->children[i] = NULL;
}
malloc_cnt++;
return tmp;
}

void add_suffix_string_to_tree(NODE *node, NODE *par_node, char *str, int len) {
int i, match_cnt;
NODE* new_node;
if(len == 0) { return; }
if(node->len != -1) { //node->len = -1 ==> root
match_cnt = prefix_match_cnt(str, node->word, len, node->len);
if(match_cnt == len) { return; } //The string is already present in the tree. return 
//we are here ==> (match_cnt < len), (match_cnt <= node->len). 
str = &str[match_cnt];
len -= match_cnt;
if(match_cnt < node->len) {
//split the current node with match_cnt length
new_node = create_node(node->word, match_cnt);
par_node->children[node->word[0] - 'a'] = new_node;
node->word += match_cnt;
node->len -= match_cnt;
new_node->children[node->word[0] - 'a'] = node;
node = new_node;
}
}
i = (str[0] - 'a');
if(node->children[i] == NULL) {
node->children[i] = create_node(str, len);
} else {
add_suffix_string_to_tree(node->children[i], node, str, len);
}
}

void add_all_suffixes_to_tree(NODE *root, char *str) {
int i, len = strlen(str);
for(i = 0; i < len; i++) {
add_suffix_string_to_tree(root, NULL, &str[i], (len - i));
}
}

void traverse_all_substrings(NODE *node, char *out, int len, TRAVERSE_FUNC func) {
int i;
if(node == NULL) { return; }
if(node->len == -1) {
for(i = 0; i < 26; i++) {
traverse_all_substrings(node->children[i], out, len, func);
}
} else {
strncpy(&out[len], node->word, node->len);
for(i = 0; i < node->len; i++) {
func(out, len + (i + 1));
}
for(i = 0; i < 26; i++) {
traverse_all_substrings(node->children[i], out, len + (node->len), func);
}
}
}

void print_substring(char *str, int len) {
char c = str[len];
str[len] = '\0';
printf("%s\n", str);
str[len] = c;
}

int total_substr_cnt = 0;
void cnt_substrings(char *str, int len) {
total_substr_cnt++;
}

int substr_cnt = 0;
void handle_substring(char *str, int len) {
char c = str[len];
HASH_NODE *item;
substr_cnt++;
item = get_hash_table_entry(substr_cnt);
if(item) { 
str[len] = '\0';
strcpy(item->val, str);
str[len] = c;
return; 
}
}

char* chomp(char * str) {
int len = strlen(str);
if((len > 0) && (str[len - 1] == '\n')) { str[len - 1] = '\0'; }
if((len > 1) && (str[len - 2] == '\r')) { str[len - 2] = '\0'; }
return str;
}

char* convert_to_lower(char* str) {
int len = strlen(str), i;
for(i = 0; i < len; i++) {
str[i] = tolower(str[i]);
}
return str;
}

FILE *file_open(char *filename, char *mode) {
FILE *fp = fopen(filename, mode);
if(fp == NULL) {
perror("file_open");
exit(0);
}
return fp;
}

int main(int argc, char **argv) {
int num_words, num_queries, tmp;
char *str;
int query_idx = 0, idx;
HASH_NODE *item;
FILE *fp = stdin;
if(argc > 1) {
fp = file_open(argv[1], "r");
}
fgets(input, 3000, fp);
num_words = tmp = atoi(input);
// printf(":%d:\n", num_words);
tree_root = create_node(NULL, -1); //Root marker
while(tmp > 0) {
tmp--;
fgets(input, 3000, fp);
chomp(input);
convert_to_lower(input);
//printf("Adding \"%s\" ....", input);
str = malloc(sizeof(char) * 3000);
strcpy(str, input);
add_all_suffixes_to_tree(tree_root, str);
//printf("Done\n");
}
total_substr_cnt = 0;
traverse_all_substrings(tree_root, output, 0, cnt_substrings);
/* printf("OUTPUT:\n____________________\n");
traverse_all_substrings(tree_root, output, 0, print_substring);
printf("\n____________________\n");*/
fgets(input, 3000, fp);
num_queries = tmp = atoi(input);
// printf(":%d:\n", num_queries);
while(tmp > 0) {
tmp--;
fgets(input, 3000, fp);
chomp(input);
// printf("%s: ", input);
queries[query_idx] = atoi(input);
insert_into_hash_table(queries[query_idx]);
query_idx++;
}
// print_keys_in_hash_table();
// printf("total_substr_cnt: %d\n", total_substr_cnt);

substr_cnt = 0;
traverse_all_substrings(tree_root, output, 0, handle_substring);
for(idx = 0; idx < query_idx; idx++) {
item = get_hash_table_entry(queries[idx]);
printf("%s\n", item->val);
}
//Free all the memory if you have free time ;)
// printf("Malloc Count: %d \n", malloc_cnt);
// getchar();
return 0;
}

Comments :

Post a Comment