PROBLEM LINK:
Editorialist: tkh_iem
DIFFICULTY:
Hard
PREREQUISITES:
String, Suffix Structure, Bucket Sort, LCP.
PROBLEM:
You are given a string and you’ve to calculate the number of distinct substrings in each prefix of the given string.
EXPLANATION:
We need to create suffix array using bucket sort which takes O(nLogn) time, otherwise, if we use any standard sort function then it consumes O(nLognLogn) complexity which will not work here.
Then we create LCP array using suffix array and given string in linear time. For creating LCP array in linear time we can use Kasai’s algorithm as well.
COMPLEXITY:
O(nlogn) where n is the length of the string.