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

typedef struct Trie {
    char letter;
    bool is_final;
    struct Trie* child;
    struct Trie* next;
} Trie;

void init_trie(Trie** root) {
    *root = (Trie*)calloc(1, sizeof(Trie));
}

void add_word(Trie** root, char* word) {
    int i = 0;
    Trie* cur_trie = *root;
    for (i = 0; i < strlen(word); ++i) {
        if (cur_trie->child == NULL) {
            cur_trie->child = (Trie*)calloc(1, sizeof(Trie));
            cur_trie->child->letter = word[i];
            cur_trie = cur_trie->child;
        }
        else {
            Trie* last_trie = cur_trie->child;
            cur_trie = cur_trie->child;
            while (cur_trie && cur_trie->letter != word[i]) {
                last_trie = cur_trie;
                cur_trie = cur_trie->next;
            }
            if (cur_trie == NULL) {
                last_trie->next = (Trie*)calloc(1, sizeof(Trie));
                cur_trie = last_trie->next;
                cur_trie->letter = word[i];
            }
        }
    }
    cur_trie->is_final = true;
}


int contains(Trie* root, char* word) {
    int i = 0;
    Trie* cur_trie = root;
    for (i = 0; i < strlen(word); ++i) {
        if (cur_trie->child == NULL) {
            return 0;
        }
        else {
            cur_trie = cur_trie->child;
            while (cur_trie && cur_trie->letter != word[i]) {
                cur_trie = cur_trie->next;
            }
            if (cur_trie == NULL) {
                return 0;
            }
        }
    }
    return cur_trie->is_final == true;
}


void remove_word(Trie** root, char* word) {
    int i = 0;
    Trie* cur_trie = *root;
    for (i = 0; i < strlen(word); ++i) {
        if (cur_trie->child == NULL) {
            return;
        }
        else {
            cur_trie = cur_trie->child;
            while (cur_trie && cur_trie->letter != word[i]) {
                cur_trie = cur_trie->next;
            }
            if (cur_trie == NULL) {
                return;
            }
        }
    }
    cur_trie->is_final = false;
}

char* longest_word_helper(Trie* root, int is_root) {
    if (root == NULL) {
        return NULL;
    }
    char* word = NULL;
    if (root->child == NULL) {
        if (is_root || root->is_final == false) {
            return NULL;
        }
        word = (char *)malloc(2);
        word[0] = root->letter;
        word[1] = '\0';
        return word;
    }
    int max_len = -1;
    char* cur_word = NULL;
    Trie* cur_tree = root->child;
    while (cur_tree) {
        char* w = longest_word_helper(cur_tree, 0);
        int len = w == NULL ? 0 : strlen(w);
        if (len > max_len) {
            max_len = len;
            cur_word = w;
        }
        cur_tree = cur_tree->next;
    }
    if (cur_word) {
        if (is_root) {
            return cur_word;
        }
        word = (char *)malloc(max_len + 2);
        word[0] = root->letter;
        memcpy(word + 1, cur_word, max_len);
        word[max_len + 1] = '\0';
        return word;
    }
    else {
        if (root || root->is_final == false) {
            return NULL;
        }
        word = (char*)malloc(2);
        word[0] = root->letter;
        word[1] = '\0';
        return word;
    }
    return NULL;
}

char* longest_word(Trie* root) {
    return longest_word_helper(root, 1);
}

int main()
{
    Trie* t = NULL;
    init_trie(&t);
    add_word(&t, "vladimir");
    add_word(&t, "ura");
    add_word(&t, "vladimir");
    add_word(&t, "ppp");
    add_word(&t, "aaa");
    add_word(&t, "uradsad");
    add_word(&t, "facultate");
    add_word(&t, "sd");
    remove_word(&t, "aaa");
    printf("%d ", contains(t, "facultate"));
    printf("%d ", contains(t, "ppp"));
    printf("%d ", contains(t, "pppp"));
    printf("%d ", contains(t, "ura"));
    printf("%d ", contains(t, "ura1"));
    printf("%d ", contains(t, "vladimir"));
    printf("%d ", contains(t, "vladimir1"));
    printf("%s ", longest_word(t));
    return 0;
}