uva 10405-Longest common subsequence-solution hints

https://uva.onlinejudge.org/external/104/10405.pdf


Nothing to say about this programme .

Just learn the LCS(longest common subsequence) algorithm and follow the steps it will be solved .

for more information about LCS just visit the site given below :

http://www.thecrazyprogrammer.com/2015/05/c-program-for-longest-common-subsequence-problem.html

An accepted code is given below for better understand :

#include<iostream>
#include<string>
#include<stdio.h>
#define s 1002
using namespace std;

long long int c[s][s];

int maxi(int x , int y)
{
    if(x>=y)
    {
        return x;
    }
    else
    {
        return y;
    }
}

void lcs(string a , string b)
{
    int m,n;

    m=a.length();
    n=b.length();

    for(int i=0;i<=m;i++)
    {
        c[i][0]=0;
    }

    for(int i=0;i<=n;i++)
    {
        c[0][i]=0;
    }

    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
            }
            else if(a[i-1]!=b[j-1])
            {
                c[i][j]=maxi(c[i-1][j],c[i][j-1]);
            }
        }
    }

    printf("%d\n",c[m][n]);
}

int main()
{
    string a,b;

    while(getline(cin,a))
    {
        getline(cin,b);

        lcs(a,b);
    }

    return 0;
}