xuanquang1999's blog

By xuanquang1999, history, 6 years ago, In English

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.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it