Longest common subsequence problem.

Problem Statement: Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Solution #1: A Brute force approach will take exponential time to solve this problem. We will use dynamic programming to solve it in O(mn) time and space. Below is the equation and the code for the problem,


LCS[i, j] = LCS[i-1][j-1] + 1 ; arr1[i] == arr2[j]
               = MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise

#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}