ZeroJudge A252: Another LCS

The standard LCS problem (Longest Common Subsequence) is to find the longest common subsequence between two given strings.

To clarify the definition of a subsequence, consider the string "abccdd": "abc," "adda," "aca," "bda," and similar examples are its subsequences. However, "adc," "bdde," "bddd," and others are not subsequences of it.

For the two strings "accbbeffg" and "fcebg," their Longest Common Subsequence (LCS) has a length of 3, and the LCS could be "cbg" or "ceg."

Let's make the problem a bit more challenging: given three strings, find the length of their Longest Common Subsequence (LCS).

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
Each test case file contains only one test case. Each test case consists of three strings. It is guaranteed that the length of all three strings does not exceed 100, and the strings are all composed of lowercase letters.For each test case, output the length of the Longest Common Subsequence (LCS).
abe
acb
babcd		2
ZeroJudge A252 Sample Test Case

Thought Process

If the three characters at the current positions are equal, we check whether any of the indices i, j, or k are 0. If any of these are 0, we set the value of the 3D array at [i][j][k] to 1. Otherwise, we set the value of the 3D array at [i][j][k] to the value of [i-1][j-1][k-1].

If the characters at the current positions are not equal, we also check if any of i, j, or k are 0. If none of them are 0, we set the value of the 3D array at [i][j][k] to the value at [i-1][j-1][k-1]. Additionally, if one or two of i, j, or k are 0, we set the value to that of the non-zero index at [i-1], [j-1], or [k-1]. If all are 0, we set the 3D array at [i][j][k] to 0.

The final answer is the value stored in the 3D array at position [a.length()-1][b.length()-1][c.length()-1].

Sample Code－ZeroJudge A252: Another LCS

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string a, b, c;
    cin >> a >> b >> c;
    int DP[100][100][100] = {};
    for (int i = 0; i<a.length(); i++) {
        for (int j = 0; j<b.length(); j++) {
            for (int k = 0; k<c.length(); k++) {
                if (a[i] == b[j] && b[j] == c[k]) {
                    if (i > 0 && j > 0 && k > 0) {
                        DP[i][j][k] = DP[i-1][j-1][k-1];
                    }
                    else {
                        DP[i][j][k] = 0;
                    }
                    DP[i][j][k]++;
                }
                else {
                    if (i > 0 && j > 0 && k > 0) {
                        DP[i][j][k] = max(max(DP[i-1][j][k], DP[i][j-1][k]), DP[i][j][k-1]);
                    }
                    else if (i > 0 && j > 0) {
                        DP[i][j][k] = max(DP[i-1][j][k], DP[i][j-1][k]);
                    }
                    else if (j > 0 && k > 0) {
                        DP[i][j][k] = max(DP[i][j-1][k], DP[i][j][k-1]);
                    }
                    else if (i > 0 && k > 0) {
                        DP[i][j][k] = max(DP[i-1][j][k], DP[i][j][k-1]);
                    }
                    else if (i > 0) {
                        DP[i][j][k] = DP[i-1][j][k];
                    }
                    else if (j > 0) {
                        DP[i][j][k] = DP[i][j-1][k];
                    }
                    else if (k > 0) {
                        DP[i][j][k] = DP[i][j][k-1];
                    }
                    else DP[i][j][k] = 0;
                }
            }
        }
    }
    cout << DP[a.length()-1][b.length()-1][c.length()-1] << "\n";
}

//ZeroJudge A252
//Dr. SeanXD
Tags

Related Posts

Comments