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*|^{2}) 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.