Seriously, why so serious? And why so mainstream? Competitive programming is all about fun, therefore...

Cutting to the chase

I'll talk about something that goes like that: everyone talks about it, few really know how to do it, everyone thinks everybody else knows how to do it, so everyone claims they know how to do it.Not teenage sex, but understanding data structures. In the sense of the metaphor before, I am close to a virgin but I still can give you some insight as there are some structures that are my type.

Don't get me wrong, I am not talking about mainstream stuff like segment trees, but not so usual data structure that tend to be implemented and modeled exactly the same way each time or even not implemented(cause STL has them). So, we're gonna talk about tries and heaps.

The good ol' dictionary

We'll try to implement a structure that can handle the following queries:

• add(w) — add an apparition of word w in the data structure
• delete(w) — delete an apparition of word w in the data structure
• ask(w) — get the number of apparition of word w in the list
• lcp(w) — get a word from the data structure that has the longest common prefix with string w

Let's ignore the 4th type of query.

Now what's the simplest way to do this? Keep a list an loop through it. Nothing wrong with that, but we need faster stuff. The obvious thing that a programmer would think at is giving the words some order so that the search is faster. This is exactly what STL's unordered_map does. So a map would to the business. Supposing you want to implement it yourself, you should find a nice hashing function the problem might be solved. OK, I'll go home, we're done.

Give it a trie

At this moment we have a decent data structure but we did not solved the 4th query. Also, we did not use one information: we are working with strings. Now we need some observation to go on: if some strings have a common prefix, the prefix should be stored only once and we would need to somehow point to more places from that position.