Light OJ 1110 - An Easy LCS

LCS:  An Easy LCS

This is an interesting LCS dp for problem for beginner. There is many solution for this problem. In problem this firstly we calculate the size of LCS using recursively.

1. string A, B;
3. int n, m;
4. int dp[102][102];
6. int lcs(int i, int j)
7. {
8.     if (i == n + 1 || j == m + 1) {
9.         return 0;
10.     }
11.     if (dp[i][j] != -1) return dp[i][j];
12.     int x = 0;
13.     if (A[i] == B[j]) {
14.         x = lcs(i + 1, j + 1) + 1;
15.     }
16.     else {
17.         x = max(lcs(i + 1, j), lcs(i, j + 1));
18.     }
19.     dp[i][j] = x;
20.     return x;
21. }

Then we start to use a to z for getting lexicographically smallest LCS. First we try to use a whether a is the part of LCS and then b and so on. For more clear to you code is given.

1. for (int i = 0; i < k; i++) {
2.             for (int j = 'a'; j <= 'z'; j++) {
3.                 ck = 0;
4.                 x = a;
5.                 while (A[x]) {
6.                     if (A[x] == j) {
7.                         ck++;
8.                         break;
9.                     }
10.                     x++;
11.                 }
12.                 y = b;
13.                 while (B[y]) {
14.                     if (B[y] == j) {
15.                         ck++;
16.                         break;
17.                     }
18.                     y++;
19.                 }
20.                 if (ck == 2) {
21.                     if (dp[a][b] == dp[x][y]) {
22.                         res += A[x];
23.                         a = x + 1;
24.                         b = y + 1;
25.                         break;
26.                     }
27.                 }
28.             }
29.         }