Problem link : contest practice Difficulty : Medium Prerequisites : Suffix Automaton Problem : Given a string S and N queries. Each query is defined by two integers  L_{i} and P_{i}. Count the number of strings of the length L_{i} that occur exactly P_{i} times (as the consecutive substrings) in the string S. ExplanationThis problem is the hardest in the set. At least, according to my estimations. There are some simple solutions that can be coded without putting a lot of effort, though, so let's consider them first. How to get 13 pointsThe constraints are very low, so you can do a pure brute force. For example, you can store all the substrings in the STL map along with the number of their occurences and when you get a query, you can iterate through all the substrings in the map and for the each of them you can check that the length and the number of occurences is the same with what is asked in the corresponding query. How to get 40 pointsNow N is larger so we have to store the information about all the substrings in the more efficient way. For example, using a trie. It is possible to construct the trie, containing all the suffixes (=all the substrings) of the string S in O(S^{2}) time. Moreover it's possible to store the depth and the number of occurences of the associated substring for each trie's node. Knowing that there will be no more than O(S^{2}) such pairs, we can just count the amount of occurences of each pair and then answer queries in O(1) time. How to get 100 pointsHere we need some suffix structure in order to store the information about the substrings. Writer's choice is the suffix automaton. The complete its' description is beyond this editorial, because it requires a lot of space and theoretical results. So, from now on, we will consider that you're familiar with the suffix automaton. If you're not, here are some basic facts that will be crucial in out solution:
Knowing this, we obtain the following solution:
This new problem can be solved different. One of the ways is to note that different Xcoordinates' segments are independent. So we can solve the 1D case of this problem. While solving the 1D case, it's easy to see that the number of the segments that cover the point X equals to AB, where A equals to the number of the segments that end later or equal than in X and B equals to the number of the segments that begin after X. Related linksasked 29 Jun '14, 14:01

Is there any way of doing it using suffix array . answered 29 Jun '14, 18:16

The way I feel about these LunchTime contests is ,more or less like you, that they are targeted at very skilled school kids only... I am now finishing my Bachelor's degree and I've never even implemented a trie on my own as far as I recall. And I have finished both my two algorithm subjects with grades nearing 80% so, it seems to me that these contests just show that A LOT of hard work is required on your own if you want to succeed in programming contests... That and not having some more decent adhoc logic... which really impares my performance... But maybe this is the goal of the contest too: to show that these contests are not for everyone and that having good grades at uni and interest is not even enough to perform well... Bruno answered 01 Jul '14, 20:51

Hey ! I submitted the following code , don't understand why it is wrong ?
answered 15 Jul '14, 22:29
