How to solve this variant of LCS?

Revision en3, by xuanquang1999, 2018-09-14 17:18:14

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?

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 xuanquang1999 2018-09-14 17:18:14 1 Tiny change: ' \leq |T|$). \n\nI ca' -> ' \leq |T|$. \n\nI ca'
en2 xuanquang1999 2018-09-14 17:17:33 83
en1 xuanquang1999 2018-09-14 17:16:41 588 Initial revision (published)