Longest common subsequence using dynamic programming C code

 

Longest common subsequence using dynamic programming C code

Let S1=abcca

      S2=abcc

Longest common subsequence between S1 and S2 is length 4.

#include<stdio.h>

#include<string.h>

int i,j;

void main()

{

    char str1[10];

    char str2[10];

    int m ;

    int n;

    printf("enter string1");

    scanf("%s",str1);

    printf("enter string2");

    scanf("%s",str2);

    m=strlen(str1);

    n=strlen(str2);

    lcs(m,n,str1,str2);

}

lcs(int m,int n,char str1[],char str2[])

{

    int dp[10][10];

     for(i=0;i<=m;i++)

     {

        for(j=0;j<=n;j++)

        {

            if(i==0||j==0)

                dp[i][j]=0;

            else if(str1[i]==str2[j])

            {

                 dp[i][j]=dp[i-1][j-1]+1;

            }

            else if(dp[i-1][j]>dp[i][j-1])

                {

                    dp[i][j]=dp[i-1][j];

                }

                else

                {

                    dp[i][j]=dp[i][j-1];

                }

            }

        }

     printf("%d",dp[m][n]);

}