C++::data_structures::Trie

trie.cpp

struct node {
    node *children[26];
    int words;
    int prefixes;
};

struct trie {
    node *root;
};

void trie_initialize(node *tNode) {
    tNode->words = 0;
    tNode->prefixes = 0;
    for (int i = 0; i < 26; ++i) {
        tNode->children[i] = 0;
    }
}

void trie_add_word(node *tNode, string &word, int i) {
    if (i == word.size()) {
        tNode->words++;
        return;
    }

    tNode->prefixes++;
    int pos = word[i] - 'a';
    node *nNode = tNode->children[pos];
    if (nNode == 0) {
        nNode = new node;
        tNode->children[pos] = nNode;
        trie_initialize(tNode->children[pos]);
    }
    trie_add_word(nNode, word, i + 1);
}

void trie_add_word(node *root, string &word) {
    trie_add_word(root, word, 0);
}

int trie_count_words(node *tNode, string &word, int i) {
    if (i == word.size()) {
        return tNode->words;
    }

    int pos = word[i] - 'a';
    if (tNode->children[pos] == 0) {
        return 0;
    }
    return trie_count_words(tNode->children[pos], word, i + 1);
}

int trie_count_words(node *root, string &word) {
    return trie_count_words(root, word, 0);
}

int trie_count_prefixes(node *tNode, string &word, int i) {
    if (i == word.size()) {
        return tNode->prefixes;
    }

    int pos = word[i] - 'a';
    if (tNode->children[pos] == 0) {
        return 0;
    }
    return trie_count_prefixes(tNode->children[pos], word, i + 1);
}

int trie_count_prefixes(node *root, string &word) {
    return trie_count_prefixes(root, word, 0);
}