**PROBLEM LINK:** Gru and his Robbery of Mars

**AUTHOR:** panik

**DIFFICULTY:** Hard

**PREREQUISITES:** Suffix Tree, DFS

**Expected Solution:** In this problem after every query, suffixes in the string increases,

without altering the already present suffixes, since the query string is appended in the front of the string S.

We will use the suffix tree data structure for this problem. Now if after

every query we add new suffixes to the suffix tree, this would lead to an O(N^2)

algorithm which would not satisfy the constraints. To, tackle this obstacle we think

the problem in reverse. We store all the queries and make the suffix tree of the final

string, and for each query in reverse order delete the suffixes from the tree one by

one(up to the length of the query string) and give answer to the queries in reverse

order. This method will work because, the suffix tree contains at most 2*N nodes so

the whole process of deletion of nodes will take O(N) complexity. Now to answer any

query, we know that the sum of the length of all the edges in the suffix tree gives the

no. of distinct sub-strings in the current string, so while deleting nodes we will keep

track of this count as well and hence answer the query in O(1).

So our core logic has O(N) complexity while building a suffix tree has O(NlogN)

complexity(O(N) if we use ukonen algorithm). Also note that we need to store the

address of last node for each suffix added while suffix tree is being constructed using

suffix array+lcp(longest common prefix), so that when we need to delete a specific

suffix, we can easily find the last node of that suffix and delete nodes until we find a

node with more than 1 children.

So overall complexity is O(NlogN).

**Expected solution**: here