{"id":822,"date":"2024-10-14T14:28:26","date_gmt":"2024-10-14T08:58:26","guid":{"rendered":"https:\/\/codexplained.in\/?p=822"},"modified":"2025-11-24T15:42:25","modified_gmt":"2025-11-24T10:12:25","slug":"find-highest-common-subsequence","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=822","title":{"rendered":"Find Highest Common Subsequence"},"content":{"rendered":"\n

Key Concepts of Longest Common Subsequence<\/h3>\n\n\n\n
    \n
  1. Subsequence<\/strong>: A subsequence is a sequence derived from another sequence by deleting some elements without changing the order of the remaining elements.<\/li>\n\n\n\n
  2. Dynamic Programming<\/strong>: The LCS problem can be efficiently solved using a dynamic programming approach. We create a 2D array where each cell represents the length of the LCS of substrings of the two given strings.<\/li>\n<\/ol>\n\n\n\n

    Dynamic Programming Approach<\/h3>\n\n\n\n
      \n
    • Step 1<\/strong>: Create a 2D array dp<\/code> where dp[i][j]<\/code> will hold the length of LCS of the first i<\/code> characters of string X<\/code> and the first j<\/code> characters of string Y<\/code>.<\/li>\n\n\n\n
    • Step 2<\/strong>: Fill this array based on the following rules:\n
        \n
      • If the characters match (X[i-1] == Y[j-1]<\/code>), then: dp[i][j]=dp[i\u22121][j\u22121]+1dp[i][j] = dp[i-1][j-1] + 1dp[i][j]=dp[i\u22121][j\u22121]+1<\/li>\n\n\n\n
      • If they don\u2019t match, then: dp[i][j]=max\u2061(dp[i\u22121][j],dp[i][j\u22121])dp[i][j] = \\max(dp[i-1][j], dp[i][j-1])dp[i][j]=max(dp[i\u22121][j],dp[i][j\u22121])<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Step 3<\/strong>: The value in dp[m][n]<\/code> (where m<\/code> and n<\/code> are the lengths of the strings) will be the length of the LCS.<\/li>\n<\/ul>\n\n\n\n

        C Program to Find Longest Common Subsequence<\/h3>\n\n\n
        \n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\n\/\/ Function to find the length of Longest Common Subsequence\nint longestCommonSubsequence(char* X, char* Y) {\n    int m = strlen(X);\n    int n = strlen(Y);\n    \n    \/\/ Create a 2D array to store lengths of longest common subsequence\n    int** dp = (int**)malloc((m + 1) * sizeof(int*));\n    for (int i = 0; i <= m; i++) {\n        dp[i] = (int*)malloc((n + 1) * sizeof(int));\n    }\n\n    \/\/ Build the dp array\n    for (int i = 0; i <= m; i++) {\n        for (int j = 0; j <= n; j++) {\n            if (i == 0 || j == 0) {\n                dp[i][j] = 0; \/\/ Base case\n            } else if (X[i - 1] == Y[j - 1]) {\n                dp[i][j] = dp[i - 1][j - 1] + 1; \/\/ Characters match\n            } else {\n                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; \/\/ Characters don't match\n            }\n        }\n    }\n\n    \/\/ Length of LCS is in dp[m][n]\n    int lcsLength = dp[m][n];\n\n    \/\/ Free the allocated memory for dp\n    for (int i = 0; i <= m; i++) {\n        free(dp[i]);\n    }\n    free(dp);\n\n    return lcsLength;\n}\n\n\/\/ Function to print the LCS itself\nvoid printLCS(char* X, char* Y) {\n    int m = strlen(X);\n    int n = strlen(Y);\n    \n    \/\/ Create a 2D array to store lengths of longest common subsequence\n    int** dp = (int**)malloc((m + 1) * sizeof(int*));\n    for (int i = 0; i <= m; i++) {\n        dp[i] = (int*)malloc((n + 1) * sizeof(int));\n    }\n\n    \/\/ Build the dp array\n    for (int i = 0; i <= m; i++) {\n        for (int j = 0; j <= n; j++) {\n            if (i == 0 || j == 0) {\n                dp[i][j] = 0; \/\/ Base case\n            } else if (X[i - 1] == Y[j - 1]) {\n                dp[i][j] = dp[i - 1][j - 1] + 1; \/\/ Characters match\n            } else {\n                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; \/\/ Characters don't match\n            }\n        }\n    }\n\n    \/\/ Now, reconstruct the LCS from the dp array\n    int index = dp[m][n];\n    char* lcs = (char*)malloc((index + 1) * sizeof(char));\n    lcs[index] = '\\0'; \/\/ Null-terminate the string\n\n    int i = m, j = n;\n    while (i > 0 && j > 0) {\n        if (X[i - 1] == Y[j - 1]) {\n            lcs[index - 1] = X[i - 1]; \/\/ Store this character in lcs\n            i--;\n            j--;\n            index--;\n        } else if (dp[i - 1][j] > dp[i][j - 1]) {\n            i--; \/\/ Move up in the dp array\n        } else {\n            j--; \/\/ Move left in the dp array\n        }\n    }\n\n    printf("Longest Common Subsequence: %s\\n", lcs);\n\n    \/\/ Free the allocated memory\n    for (int i = 0; i <= m; i++) {\n        free(dp[i]);\n    }\n    free(dp);\n    free(lcs);\n}\n\n\/\/ Main function\nint main() {\n    char X[100], Y[100];\n\n    \/\/ Input the two strings\n    printf("Enter first string: ");\n    fgets(X, sizeof(X), stdin);\n    X[strcspn(X, "\\n")] = '\\0'; \/\/ Remove newline character\n\n    printf("Enter second string: ");\n    fgets(Y, sizeof(Y), stdin);\n    Y[strcspn(Y, "\\n")] = '\\0'; \/\/ Remove newline character\n\n    \/\/ Find the length of LCS\n    int lcsLength = longestCommonSubsequence(X, Y);\n    printf("Length of Longest Common Subsequence: %d\\n", lcsLength);\n\n    \/\/ Print the LCS itself\n    printLCS(X, Y);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
        Explanation of the Code<\/h3>\n\n\n\n
          \n
        1. Dynamic Programming Table<\/strong>:\n
            \n
          • The program uses a 2D array dp<\/code> where dp[i][j]<\/code> stores the length of the LCS of the first i<\/code> characters of string X<\/code> and the first j<\/code> characters of string Y<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Building the DP Array<\/strong>:\n
              \n
            • The nested loops populate the dp<\/code> array based on whether characters match or not. The base case is when one of the strings is empty.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Reconstructing the LCS<\/strong>:\n
                \n
              • After filling the dp<\/code> table, the program reconstructs the LCS by tracing back through the dp<\/code> array.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • Memory Management<\/strong>:\n
                  \n
                • The program frees the allocated memory for the dp<\/code> array and the LCS string to prevent memory leaks.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                  Input and Output Example<\/h3>\n\n\n\n
                  Input<\/h4>\n\n\n\n
                  cCopy codeEnter first string: AGGTAB\nEnter second string: GXTXAYB\n<\/code><\/pre>\n\n\n\n
                  Output<\/h4>\n\n\n\n
                  mathematicaCopy codeLength of Longest Common Subsequence: 4\nLongest Common Subsequence: GTAB\n<\/code><\/pre>\n\n\n\n
                  Conclusion<\/h3>\n\n\n\n
                  This C program efficiently computes the Longest Common Subsequence of two strings using dynamic programming. It allows for user input and displays both the length and the actual LCS. You can test different pairs of strings to see how the LCS changes. This approach is suitable for various applications requiring sequence analysis.<\/p>\n