Program Overview

This program finds the longest common subsequence (LCS) between two strings using dynamic programming. The LCS is the longest sequence that appears in both strings in the same order, but not necessarily consecutively.

Program Structure

• Input: Two strings for which the LCS needs to be found.
• Dynamic Programming Table: A 2D array to store the lengths of longest common subsequences for different substrings.
• Output: The length of the longest common subsequence.

C Program

#include 
#include 

// Function to find the length of the longest common subsequence
int longestCommonSubsequence(char *X, char *Y, int m, int n) {
    int L[m + 1][n + 1]; // DP table to store lengths of longest common subsequence

    // Build the LCS table in bottom-up fashion
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) { // Base case: if either string is empty if (i == 0 || j == 0) { L[i][j] = 0; } // If the characters match, increase the length by 1 else if (X[i - 1] == Y[j - 1]) { L[i][j] = L[i - 1][j - 1] + 1; } // If characters do not match, take the maximum of the two possibilities else { L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];
            }
        }
    }

    return L[m][n]; // The length of the LCS is in L[m][n]
}

// Main function
int main() {
    char X[100], Y[100];
    
    // Input the two strings
    printf("Enter first string: ");
    scanf("%s", X);
    printf("Enter second string: ");
    scanf("%s", Y);

    int m = strlen(X);
    int n = strlen(Y);

    // Calculate the length of the longest common subsequence
    int lcsLength = longestCommonSubsequence(X, Y, m, n);
    printf("Length of Longest Common Subsequence: %d\n", lcsLength);

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for calculating the LCS and the main function to handle input and output:

• The longestCommonSubsequence function implements the dynamic programming approach:
  • A 2D array L is created to store the lengths of the longest common subsequences for substrings of X and Y.
  • The function iterates through each character of the two strings. If characters match, it increments the count by 1 from the diagonal value in the table. If they do not match, it takes the maximum value from either the left or above cell in the table.
• The main function handles user input:
  • The user is prompted to enter two strings.
  • It calculates the length of the longest common subsequence by calling the longestCommonSubsequence function and displays the result.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the two strings.
3. The program will output the length of the longest common subsequence between the two strings.