I'm trying to solve the problem 101237G — Total LCS from 2013-2014 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest. The task give two string S and T, each with at most 2000 character, and ask to compute the longest common subsequence (LCS) of string S and substring T[i..j] for all pair 1 ≤ i ≤ j ≤ |T|).

I have read the code from some contestant (using coach mode) but I still have no idea how those solution work. Can anyone give me a hint?

Thanks in advance.