For the first subtask, consider all ~\mathcal{O}(N^4)~ pairs of substrings. It takes ~\mathcal{O}(N)~ to compute the length of the longest common prefix (LCP) of two of these substrings, which would be too slow. Instead, by fixing the starting position of each of the substrings and computing the running LCP, each length can be computed in ~\mathcal{O}(1)~.

Time Complexity: ~\mathcal{O}(N^4)~

For the next subtask, we think of substrings as prefixes of suffixes. For each pair of suffixes, their LCP can be computed in ~\mathcal{O}(N)~. Say that the suffixes with length ~i~ and ~j~ have an LCP of length ~k~. It is not hard to see that there are ~(i-k+1)(j-k+1)~ pairs of prefixes whose LCP is equal to ~k~ and there are ~i+j+1-2x~ pairs of prefixes whose LCP is equal to ~x~. In particular, the strings themselves are no longer important, only ~i~, ~j~, and ~k~ matter. These values can be computed and added to the answer for each length.

Time Complexity: ~\mathcal{O}(N^3)~

For the third subtask, the solution to the second subtask is sped up. A suffix tree can be constructed to compute all the LCPs of the pairs of suffixes in ~\mathcal{O}(N^2)~. The answer values found above must also be added to the answers more quickly. This can be done by noting that each term can be split into ~1~, ~x~, and ~x^2~ terms. Then these coefficients can be added to the answer values by updating a difference array instead and computing the final answer at the end.

Time Complexity: ~\mathcal{O}(N^2)~

For the final subtask, the solution can be sped up even further. A suffix array and LCP array construction can be done in ~\mathcal{O}(N)~. The LCP array only computes the LCP between two consecutive suffixes in the suffix array rather than every pair. However, the LCP between two arbitrary pairs of suffixes can easily be computed using the LCP array: If the suffixes are at index ~i~ and ~j~, their LCP is the minimum of ~LCP[i], LCP[i+1], \dots, LCP[j-1]~.

For each ~i~, consider indices ~l~ and ~r~, ~l \le i < r~, so that the LCP of the suffixes indexed at ~l~ and ~r~ is equal to ~LCP[i]~. These indices can all be computed in ~\mathcal{O}(N)~ using a stack. Observe that ~l, i, r~ describe a range of pairs of suffixes whose LCP is exactly equal to ~LCP[i]~. Then this essentially computes the LCP of any pair of suffixes. It is not hard to handle multiple pairs of suffixes at once rather than a single pair of suffixes as in the third subtask. The solution is essentially the same and the final answer can be done by updating a difference array of the answers instead and processing at the end.

Time Complexity: ~\mathcal{O}(N)~