UVA - 10405 - Longest Common Subsequence

//Problem  link >>http://uva.onlinejudge.org/external/104/10405.html

.... my  first  LCS  problem ... very  easy ...

///// LCS  using  DP....

#include <bits/stdc++.h>
using namespace std ;

int  dp[1002][1002] , x , y ;
 string s1 , s2 ;

int lcs(int i , int j)
{
    if (i==x || j==y) return 0 ;

    int  &rez=dp[i][j] ;
    if (rez !=-1) return rez ;

    if (s1[i]==s2[j])
    {
        return rez=1+lcs(i+1 , j+1) ;
    }
   return rez= max(lcs(i , j+1) , lcs(i+1 , j) ) ;
}

int main ()
{
    while (getline(cin,s1))
    {
        getline(cin,s2) ;
         x=s1.size() ;
         y=s2.size() ;

        memset(dp,-1,sizeof (dp)) ;
       cout<<lcs(0,0)<<endl ;
    }
    return 0;
}

///////  Iterative  LCS ..........

#include<iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std ;

int lcs[1002][1002] ;

int main ()
{
    string s1 , s2 ;
    while (getline(cin,s1))
    {
        getline(cin,s2) ;
        int x=s1.size() ;
        int y=s2.size() ;

        for (int i=1 ; i<=x ; i++)
        {
            for (int j=1 ; j<=y ; j++)
            {
                if (s1[i-1]==s2[j-1]) lcs[i][j]=1+lcs[i-1][j-1] ;
                else lcs[i][j]=max(lcs[i][j-1],lcs[i-1][j]) ;
            }
        }
        cout<<lcs[x][y]<<endl ;
    }
    return 0;
}

Sample input

a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

Sample output

4
3
26
14