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; }
At Board Infinity we have authors leading in their profession sharing their insights, ideas and inspiration. Here influential thinkers, creators, makers and doers are found in one place.
Subscribe to our Newsletter
Receive latest industry news and updates, exclusive offers directly in your inbox.
Get FREE Career counselling
Get in touch with our expert career counselors to make the right career choice for yourself.