As stated on the problem statement:
For a string S=c1 c2 … cN, let S[a,b] denote ca ca+1 … cb-1 cb, that is, the substring starting at ath character and ending at bth character. For each 1 ≤ i ≤ L, chef wants the children to know how many tuples (a, b, c, d) exist for which S1[a, b] = S2[c, d] and length of S1[a,b] is i.
We can use the concept of suffix arrays to solve the problem along with the use of a stack data structure to solve queries fast.
The most naive solution for this problem has complexity O(N^2) and it involves checking all possible substrings of a string on the other string.
This solution solves Subtasks 1 and 2 only…
For the remaining subtasks O(NlogN) solution needs to be devised using the concept of Suffix Arrays…
Further helpful links to consult: