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 can't come up with anything beside the naive O(|S| * |T|²) dynamic programming. 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.