The "kdcmej" character is the Longest Common Subsequence (LCS) between these two strings. It's not a given that a subsequence will be contiguous just because it's a subsequence.
Subsequence
Take the sequence S = [s1, s2, s3, s4,..., sn] into consideration.
If and only if it can be derived from the S deletion of some components, a sequence Z = z1, z2, z3, z4,...,zm> over S is a subsequence of S.
Common Subsequence
Let's say that X and Y are sequences spanning a limited number of elements. If Z is a subsequence of both X and Y, then Z is a common subsequence of X andY.
Theory
The longest common subsequence challenge aims to identify a common subsequence of all the given sequences that has the maximum length.
A well-known topic in computer science, the most extended common subsequence problem serves as the foundation for data comparison tools like the diff-utility and has uses in bioinformatics.
Algorithm
Algorithm: LCS-Length-Table-Formulation (X, Y) m := Length(X) n := Length(Y) for i = 1 to m do C[i, 0] := 0 for j = 1 to n do C[0, j] := 0 for i = 1 to m do for j = 1 to n do if xi = yj C[i, j] := C[i - 1, j - 1] + 1 B[i, j] := 'D' else if C[i - 1, j] ≥ C[i, j - 1] C[i, j] := C[i - 1, j] + 1 B[i, j] := 'U' else C[i, j] := C[i, j - 1] + 1 B[i, j] := 'L' return C and B
Algorithm: Print-LCS (B, X, i, j) if i = 0and j = 0 return if B[i, j] = 'D' Print-LCS(B, X, i-1, j-1) Print(xi) elseif B[i, j] = 'U' Print-LCS(B, X, i-1, j) else Print-LCS(B, X, i, j-1)
Top-Down Approach: Using C++
// Board Infinity #include <iostream> #include <string> #include <unordered_map> usingnamespace std; // Function to find the length of the longest common subsequence of substring // `X[0...m-1]` and `Y[0...n-1]` intLCSLength(string X, string Y, int m, int n, auto &lookup) { // return if the end of either string is reached if (m == 0 || n == 0) { return0; } // construct a unique map key from dynamic elements of the input string key = to_string(m) + "|" + to_string(n); // if the subproblem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // if the last character of `X` and `Y` matches if (X[m - 1] == Y[n - 1]) { lookup[key] = LCSLength(X, Y, m - 1, n - 1, lookup) + 1; } else { // otherwise, if the last character of `X` and `Y` don't match lookup[key] = max(LCSLength(X, Y, m, n - 1, lookup), LCSLength(X, Y, m - 1, n, lookup)); } } // return the subproblem solution from the map return lookup[key]; } intmain() { string X = "ABCBDAB", Y = "BDCABA"; // create a map to store solutions to subproblems unordered_map<string, int> lookup; cout << "The length of the LCS is " << LCSLength(X, Y, X.length(), Y.length(), lookup); return0; }
Bottom-up Approach: Using C++
// Board Infinity #include <iostream> #include <string> usingnamespace std; // Function to find the length of the longest common subsequence of substring // `X[0...m-1]` and `Y[0...n-1]` intLCSLength(string X, string Y) { int m = X.length(), n = Y.length(); // lookup table stores solution to already computed subproblems; // i.e., `lookup[i][j]` stores the length of LCS of substring // `X[0...i-1]` and `Y[0...j-1]` int lookup[m + 1][n + 1]; // first column of the lookup table will be all 0s for (int i = 0; i <= m; i++) { lookup[i][0] = 0; } // first row of the lookup table will be all 0s for (int j = 0; j <= n; j++) { lookup[0][j] = 0; } // fill the lookup table in a bottom-up manner for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // if the current character of `X` and `Y` matches if (X[i - 1] == Y[j - 1]) { lookup[i][j] = lookup[i - 1][j - 1] + 1; } // otherwise, if the current character of `X` and `Y` don't match else { lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]); } } } // LCS will be the last entry in the lookup table return lookup[m][n]; } intmain() { string X = "XMJYAUZ", Y = "MZJAWXU"; cout << "The length of the LCS is " << LCSLength(X, Y); return0; }
