C++ • DYNAMIC PROGRAMMING Longest Common Subsequence (LCS)

C++ • DYNAMIC PROGRAMMING

Longest Common Subsequence (LCS)

ALGORITHM

Longest Common Subsequence

TIME COMPLEXITY

O(m * n)

SPACE COMPLEXITY

O(m * n)

APPROACH

Dynamic Programming

C++ Implementation

longest_common_subsequence.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class SequenceLCS
{
    string s1, s2;
    int dp[105][105];

public:

    // Constructor
    SequenceLCS()
    {
        s1 = "";
        s2 = "";
    }

    // Input function
    void input()
    {
        cout << "Enter first sequence: ";
        cin >> s1;

        cout << "Enter second sequence: ";
        cin >> s2;
    }

    // Function to calculate LCS length and reconstruct the LCS string
    void findLCS()
    {
        int m = s1.length();
        int n = s2.length();

        // Building the DP table
        for (int i = 0; i <= m; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (i == 0 || j == 0)
                    dp[i][j] = 0;
                else if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        // Reconstructing the LCS string from DP table
        int index = dp[m][n];
        string lcsStr = "";
        int i = m, j = n;

        while (i > 0 && j > 0)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                lcsStr += s1[i - 1];
                i--;
                j--;
            }
            else if (dp[i - 1][j] > dp[i][j - 1])
            {
                i--;
            }
            else
            {
                j--;
            }
        }

        reverse(lcsStr.begin(), lcsStr.end());

        cout << "Length of LCS: " << dp[m][n] << endl;
        cout << "Longest Common Subsequence: " << lcsStr << endl;
    }
};

int main()
{
    SequenceLCS obj;

    obj.input();
    obj.findLCS();

    return 0;
}

Sample Input

Enter first sequence: AGGTAB
Enter second sequence: GXTXAYB

Output

Length of LCS: 4
Longest Common Subsequence: GTAB

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

#include <string>

Includes string handling support.

class SequenceLCS

Creates a class named SequenceLCS to encapsulate sequences and DP logic.

int dp[105][105];

2D array used to store lengths of longest common subsequences of sub-problems.

SequenceLCS()

Class constructor that initializes member strings to empty values.

void input()

Accepts the two input sequences/strings from the user.

if (s1[i - 1] == s2[j - 1])

If current characters match, add 1 to the result of the previous diagonal sub-problem.

dp[i][j] = max(...)

If characters don't match, take the maximum from the top or left cell.

while (i > 0 && j > 0)

Backtracks from the bottom-right corner of the DP table to reconstruct the actual LCS string.

reverse(lcsStr.begin(), ...)

Reverses the backtracked string since characters were gathered from end to start.

SequenceLCS obj;

Instantiates the SequenceLCS object and triggers the constructor.

return 0;

Signals successful program execution.

How Longest Common Subsequence works: LCS uses Dynamic Programming to build a 2D table where each cell dp[i][j] stores the length of the longest common subsequence of the prefixes s1[0..i-1] and s2[0..j-1]. By matching or skipping characters, it avoids redundant recursive calls and backtracks through the table to reconstruct the subsequence.