Deleted

I think Hirschberg algorithm can be implemented in O(n*n*log(n)) time and O(n) space. But I don't know is it enough to get AC because i don't know time limit
Function int solveLCS(String x, String y) should return whole vector K[1]. And instead of

c1 = solveLCS( x1, y.substring(0, k) ) ; // LCS of first half
c2 = solveLCS( x2, y.substring(k, n) ) ; // LCS of second half

if ( c1 + c2 == c )

there should be

c1 = solveLCS( x1, y) ; // LCS of first half
c2 = solveLCS( x2.reverse(), y.reverse() ) ; // LCS of second half

if ( c1[k] + c2[n - k] == c )

There is an algorithm faster than O(N*M). Suppose that the sequences are A and B. For each element that occurs in A write its positions in B in decreasing order.

For the given case:

5 6

1 2 3 4 1

3 4 1 2 1 3

It should look like this:

1 -> (5,3)

2 -> (4)

3 -> (6,1)

4 -> (2)

Then replace each element in A with its list:

(5,3) (4) (6,1) (2) (5,3)

5 3 4 6 1 2 5 3

Find one of its longest increasing subsequences X(There are a lot of algorithms for doing this fast like binary search, fenwick tree, segment tree and so on).

Then just print B[X1], B[X2], ..., B[Xk].

For example we can take 3, 4 and 6 as an increasing subsequence. Then we just print B[3]=1, B[4]=2 and B[6]=1 which is a valid answer.

Edit: It's not faster every time. If there is a case where all numbers in the sequences are the same it will be slower. But it's good with random test cases. When you make the list for each number you can check which of the algorithms is better to use.

There is an algo working in O(500·(N + M)). Here is the idea.

The standard DP for this problem is d[i][j] = k = LCS of S[0..i] and T[0..j]. Let's swap the parameter and the value: g[i][k] = minimal j that LCS of S[0..i] and T[0..j] = k.

Then, g[i][k] = min(g[i-1][k], nextOcc[s[i]][g[i-1][k-1]]), where nextOcc[c][j] is the position of the first occurrence of c in T after position j.