trie.cpp

#include <iostream>
#include <cstring>
#define MAX_LETTERS 600005 
#define ALPHABET_SIZE 26

using namespace std;

// These two structures should be intiialized to all 0
// (0 is the root and should never be the child of another node)
int trie[MAX_LETTERS][ALPHABET_SIZE];
bool end_word[MAX_LETTERS];
int next_node = 1;

// insert string s at the root of the trie
void insert(string s) {
    int len = s.size();
    int node = 0;
    for (int i = 0; i < len; ++i) {
        int child = s[i] - 'a';
        if (trie[node][child] == 0)
            trie[node][child] = next_node++;
        node = trie[node][child];
    }
    end_word[node] = true;
}

// check if the trie contains string s
bool contains(string s) {
    int len = s.size();
    int node = 0;
    for (int i = 0; i < len; ++i) {
        int child = s[i] - 'a';
        if (trie[node][child] == 0)
            return false;
        node = trie[node][child];
    }
    return end_word[node];
}