403670: GYM101237 G Total LCS

Let us define a function to be the length of the longest common subsequence of two strings S and T. More formally, is the length of the longest (possibly empty) string which is a subsequence of S and a subsequence of T. A string A is a subsequence of a string B if A can be obtained from B by erasing some (possibly none) characters (without permuting them!).

You are given two strings S and T. For a pair (i, j) where 1 ≤ i ≤ j ≤ |T|, let us define to be a substring of T consisting of symbols on positions from i to j inclusive.

Calculate all values of .

The two lines of input contain the strings S and T (1 ≤ |S|, |T| ≤ 2000). The strings consist of lowercase English letters.

Output the values of over all possible pairs (i, j) according to the lexicographical order of pairs (i, j).

The checking program ignores all whitespace (including line breaks), so it is up to you to format the output like a table (as we did in the example) or otherwise.

abac
cbabc

1 1 2 2 3
  1 2 2 3
    1 2 3
      1 2
        1