The Longest Common Subsequence (LCS) problem is a classic problem in computer science. It aims to find the longest subsequence present in two sequences (strings in this case) such that the subsequence appears in both strings in the same order.

Program Structure

• Input: Two strings for which we want to find the LCS.
• Output: The length of the LCS and the LCS itself.
• Dynamic Programming: The program uses a 2D array to store the lengths of longest common subsequences for different substrings.

C++ Code

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Function to find the length of LCS and the LCS itself
pair<int, string> longestCommonSubsequence(const string &s1, const string &s2) {
    int m = s1.length();
    int n = s2.length();
    
    // Create a 2D vector to store lengths of LCS
    vector<vector<int>> lcs(m + 1, vector<int>(n + 1, 0));

    // Build the lcs array in bottom-up fashion
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }

    // The length of the LCS is in lcs[m][n]
    int length = lcs[m][n];
    
    // To construct the LCS string
    string lcsString;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcsString.push_back(s1[i - 1]);
            i--;
            j--;
        } else if (lcs[i - 1][j] > lcs[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    // The LCS string is constructed in reverse order
    reverse(lcsString.begin(), lcsString.end());

    return make_pair(length, lcsString);
}

int main() {
    string str1, str2;

    // Input strings
    cout << "Enter first string: ";
    cin >> str1;
    cout << "Enter second string: ";
    cin >> str2;

    // Find LCS
    pair<int, string> result = longestCommonSubsequence(str1, str2);
    
    // Output the result
    cout << "Length of LCS: " << result.first << endl;
    cout << "Longest Common Subsequence: " << result.second << endl;

    return 0;
}

Explanation of the Code

The code consists of the following main components:

• Input Handling: The program prompts the user to enter two strings.
• LCS Calculation: The longestCommonSubsequence function uses dynamic programming to calculate the LCS. It fills a 2D vector lcs where lcs[i][j] holds the length of LCS of substrings s1[0..i-1] and s2[0..j-1].
• LCS Construction: After computing the lengths, the function constructs the LCS string by backtracking through the lcs vector.
• Output: The program displays the length of the LCS and the LCS itself.

Conclusion

This program efficiently finds the longest common subsequence using dynamic programming, making it suitable for handling larger strings compared to a naive recursive approach.