The Assignment

shefin Cefalo SUST Inter Univers...

If we extend the sub-strings s1s_1, s2s_2, and s3s_3 to the end of the string ss, the score of the sub-string triplet won’t change. So, from now on, we will consider the sub-strings as suffixes for simplicity.

Build the suffix array and corresponding LCPLCP array of the string ss. The lexicographic order of the suffixes is known now. From now on, the ithi^{th} suffix means the ithi^{th} suffix of the suffix array. Let’s say, we have chosen three suffixes ii, jj, and kk from the suffix array where i<j<ki < j < k. It will be a good sub-string triplet surely. What will be the score of it? Here, we can observe that pp is the longest common prefix of the ithi^{th} and jthj^{th} suffix, qq is the longest common prefix of the jthj^{th} and kthk^{th} suffix. And we know from the statement that the score of the sub-string triplet is p×qp\times q. Recall that the longest common prefix of any two suffixes is equal to the minimum value of the corresponding range in the LCPLCP array.

If we fix the suffix jj, we can calculate the summation of pp for all possible i<ji<j. Similarly, we can calculate the summation of qq for all possible k>jk>j. Then the summation of the scores of the good sub-string triplets where the suffix jj acts as s2s_2 will be =p×q=\sum{p} \times \sum{q}. So, if we can calculate this thing for all possible jj, we are good to go.

Let’s say, in the LCPLCP array, the value LCPiLCP_i is minimum in [L,R][L, R] range (LiR)(L \leq i\leq R), where LCPiLCP_i = longest common prefix of the ithi^{th} and (i1)th(i-1)^{th} suffix. It means, if we treat any suffix in [L1,i1][L-1, i-1] range as s1s_1 and treat any suffix in [i,R][i, R] range as s2s_2, the value of pp will be LCPiLCP_i for all of them. So, we can add LCPiLCP_i to [i,R][i,R] range. If we execute this process for each LCPiLCP_i, eventually we will get p\sum{p} for each jj. Similarly, we can also calculate q\sum{q} for each jj. As we need to get the values after all the range updates, we can apply prefix sum to perform this in O(n)\mathcal{O}(n). We can find the range [L,R][L, R] stated above for all the elements in O(n)\mathcal{O}(n) by maintaining a monotonous stack. Note that, you need to be careful about overcounting while calculating the p\sum{p} and q\sum{q}.

Time complexity: O(n×log2(n))\mathcal{O}(n \times log_2(n))


89% Solution Ratio
skb_hssnEarliest, 4M ago
Mushfiqur05Fastest, 0.1s
user.2575Lightest, 14 MB
Mushfiqur05Shortest, 2541B
Toph uses cookies. By continuing you agree to our Cookie Policy.