PROBLEM LINK:Author: Shiplu Hawlader DIFFICULTY:HARD PREREQUISITES:Suffix Array PROBLEM:We have a string of length N(<=10^5). For each index i=0 to N-1, we need to find a unique substring of minimum possible length which contains the index i. EXPLANATION:So, let's begin with Suffix Array and LCP array. This has already been explained so many times earlier and I don't think I can do better than those explanations. So here is an awesome tutorial on Suffix Arrays and LCP Array by @kuruma. If you don't know about Suffix Array don't continue before reading this tutorial. Also read about segment trees here and here. If we have build the suffix array and LCP array. Suppose three suffices of a string after making suffix array are suffix [ i - 1 ] : abccxyz... LCP( i - 1 , i) = abc So starting from index suffix[i], at most 4 length substring "abcd" are common in another position suffix[i+1]. So, we know that from suffix[i] to suffix[i]+p (both inclusive) the minimum length unique substring is p + 1.
So, we sort in increasing order of p and star updating ranges beginning from largest p.
Now, we read all values from the segment tree and suppose in a array posi we store the values taken from the segment tree.
Now posi[i] and length[i] might not be storing the optimal answer. Because second case might give us the optimal cases. Indices suffix[i]+p+1, suffix[i]+p+2, ... etc. also part of unique substrings which starts from i. In this case larger the suffix[i], smaller the substring will be. Since we need suffix[i] to be largest, we can do this in one for loop. Pseudo code:
Now, for each index we have starting(0-based index) posi[i] and length equal to length[i]. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:This pdf discusses Suffix Array and various questions in detail.
This question is marked "community wiki".
asked 17 Feb '14, 19:32 ![]()
|
I think while filling g[] you would overwrite some values. for example if p[3]=3 p[5]=5 suffix[3]=5 and suffix[5]=3 first g[8]=5 then g[8] overwrites with g[8]=3 but g[8] should have had 5 as it is closest to it answered 24 Feb '14, 23:16 ![]()
|
Can someone please provide better explaination for last part of editorial? I am unable to understand it. answered 23 Sep '17, 22:30 ![]()
|
I wrote my own solution while this was being published, haha. See
http://discuss.codechef.com/questions/38547/editorial-of-httpwwwcodechefcomcook43problemsunique-problem-is-not-found/38569