Hi. I'm beginner at competitive programming and there is 100% that this topic is not original, but, in spite of this, I decided to publish it. So, (you are still reading, that's achievement for me :D). Sometimes we need to associate string with some object and then quickly find it by those key string. Prefix trees are good thing to do it. For more information about them read this, or this.

Algorithm complexities:

Add element O(1) // iterations are equal to length of string

Remove element O(1)

Search element O(1)

Memory: In worse case each bound's weight is 300 bytes, but you can reduce this by using function to get child id by character (see in code), and saving pointer to object you are pushing.

Need a more detailed analysis, but, in generally we can see that this structure is very fast, but not so effective in memory usage, you can use it when you are need to balance memory and time.

Here is realization, hope some will use in their solution:

template <class T, std::size_t ALPHA_SIZE>
class prefix {
        public:
		prefix(std::size_t (* f)(char))
			: I(f), m_root(new node)
		{}

		~prefix() {
			rec_del(m_root);
		}

		T & operator[] (std::string s) {
			node * curr = m_root;
			for (auto e: s) {
				size_t i = I(e);
				if (curr->next[i] != nullptr) {
					curr = curr->next[i];
				} else {
					curr = curr->next[i] = new node;
				}
			}
			curr->used = 1;
			return curr->val;
		}

		bool thereis(std::string s) {
			node * curr = m_root;
			for (auto e: s) {
				size_t i = I(e);
				if (curr->next[i] != nullptr) {
					curr = curr->next[i];
				} else {
					return 0;
				}
			}
			return curr->used;
		}

	private:
		struct node {
			T val;
			uint8_t used;
			node * next[ALPHA_SIZE];
			node(): used(0) {
				for (size_t i = 0; i < ALPHA_SIZE; ++i)
					next[i] = nullptr;
			}
			~node() {}

		} * m_root;
		std::size_t (* I)(char);

		void rec_del(node * curr) {
			if (curr == nullptr) {
				return;
			} else {
				for (size_t i = 0; i < ALPHA_SIZE; ++i)
					rec_del(curr->next[i]);
			}

			delete curr;
		}
};

And this is test program.

#include <iostream>
#include <cassert>
#include <cstdio>
#include <string>

#include "prefix_tree.hpp"

inline std::size_t iofc(char c) {
	return static_cast<std::size_t>(c);
}

int main() {
	using namespace std;

	tree::prefix<int, 127> tree(iofc);

	tree["hello this is where you are!"] = 2;

	assert(tree.thereis("0000000000000000000000000000") == 0);
	assert(tree.thereis("hello this is where you are!") == 1);


	return 0;
}

Yes, many useful functions are absent, (such as remove for example, iterators). But the first step is made, so, let's improve it, good luck and have fun!