LCS

#include<stdio.h>
#include<string.h>

char st1[100],st2[100];
int len1,len2;

int LCS();
int MAX(int a,int b);

int main()
{
    printf("Enter first sequence: ");
    scanf("%s",&st1);
    printf("Enter second sequence: ");
    scanf("%s",&st2);

    len1=strlen(st1);
    len2=strlen(st2);

    int ans=0;
    ans=LCS();
    printf("LCS: %d\n",ans);

    return 0;
}

int LCS()
{
    int L[len1+1][len2+1];
    int i,j;

    for(i=0;i<=len1;i++)
        for(j=0;j<=len2;j++)
        {
            if(i==0 || j==0)
                L[i][j]=0;
            else if(st1[i-1]==st2[j-1])
                L[i][j]=L[i-1][j-1]+1;
            else
                L[i][j]=MAX(L[i-1][j],L[i][j-1]);
        }

        return L[len1][len2];
}

int MAX(int a,int b)
{
    if(a>b) return a;
    else return b;
}