PROBLEM LINK: Gru and his Robbery of Mars
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