PROBLEM LINK: Gnib It
AUTHOR: panik
DIFFICULTY: Hard
PREREQUISITES: Suffix Tree
This Question is an application of Suffix tree( other approaches might be possible, do let us know if you have something in mind). Construction of Suffix tree can be done in NLog(N) time complexity ( can also be done in O(N) using ukkonen algorithm ,but its implementation is quite long).
My implementation of suffix tree is by first construction the suffix array in NLogN and then converting it into Suffix array in O(N) by the help of LCP(Lowest common prefix) array which is also constructed in O(N). My implementation in python is of approx 120 lines, do share your approach if its more shorter.
My Suffix tree construction template: here
After the suffix tree is constructed, we calculate the no. of char below each node to obtain the no. of possible predictions for each prefix. This can be done simply by a single DFS traversal. After this, each query can be answered in O(query String length) by simply
traversing each char of substring in the suffix tree until we obtain the value stored in nodes less than X.
Refer to my code for a better explanation.
For an in-depth understanding of the topic suffix tree and suffix array refer coursera, its the best source available on the internet for these topics.
Expected solution: here