trie.cpp

#include <iostream>
#include <numeric>
#include <string>

class trie {
    struct node {
        node* children[std::numeric_limits<char>::max()] = { 0 };
        bool leaf = false;

        node* next(char c) const
        {
            return children[c];
        }

        node* add(const std::string& value, size_t ind)
        {
            if (value.size() == ind) {
                leaf = true;
                return this;
            }

            char c = value[ind];
            if (next(c) == nullptr) {
                node* new_node = new node();
                children[c] = new_node;
            }

            return next(c)->add(value, ++ind);
        }

        bool has(const std::string& value, size_t ind) const
        {
            if (value.size() == ind) {
                return leaf;
            }

            char c = value[ind];
            if (next(c) == nullptr) {
                return false;
            }

            return next(c)->has(value, ++ind);
        }
    };

    node root;

public:
    void add(const std::string& value)
    {
        root.add(value, 0);
    }

    bool has(const std::string& value) const
    {
        return root.has(value, 0);
    }
};

int main()
{

    trie t;
    std::cout << std::boolalpha << t.has("adf") << std::endl;
    t.add("aaa");
    std::cout << std::boolalpha << t.has("aaa") << std::endl;
    std::cout << std::boolalpha << t.has("aab") << std::endl;
    t.add("aab");
    std::cout << std::boolalpha << t.has("aaa") << std::endl;
    std::cout << std::boolalpha << t.has("aab") << std::endl;
    t.add("aaaa");
    std::cout << std::boolalpha << t.has("aaa") << std::endl;
    std::cout << std::boolalpha << t.has("aab") << std::endl;
    std::cout << std::boolalpha << t.has("aaaa") << std::endl;
    t.add("aabaaa");
    std::cout << std::boolalpha << t.has("aaa") << std::endl;
    std::cout << std::boolalpha << t.has("aab") << std::endl;
    std::cout << std::boolalpha << t.has("aaaa") << std::endl;
    std::cout << std::boolalpha << t.has("aabaaa") << std::endl;
    t.add("bbba");
    std::cout << std::boolalpha << t.has("aaa") << std::endl;
    std::cout << std::boolalpha << t.has("aab") << std::endl;
    std::cout << std::boolalpha << t.has("aaaa") << std::endl;
    std::cout << std::boolalpha << t.has("aabaaa") << std::endl;
    std::cout << std::boolalpha << t.has("bbba") << std::endl;
}