code-store-house: LCS

UVA- 111 : History Grading

//Problem link >>http://uva.onlinejudge.org/external/1/111.html

... here u may face this problem ... how to take input ... for the 1st student that is 3rd line of input we take the first integer ... then using for loop take the rest ... and here we're using array indexing technic to mange input ... then simple LCS ...

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

int lcs[25][25]={0} ;

int main ()
{
int n , j , i , a[50] , b[50] , x ;

cin>>n ;
for (i=1 ; i<=n ; i++)
{
cin>>x ;
a[x]=i ;
}

while (cin>>x && x!= EOF)
{
b[x]=1 ;
for (i=2 ; i<=n ;i++)
{
cin>>x ;
b[x]=i ;
}

for (i=1 ; i<=n ; i++)
{
for (j=1 ; j<=n ; j++)
{
if (a[i]==b[j]) lcs[i][j]=1+lcs[i-1][j-1] ;
else lcs[i][j]=max(lcs[i][j-1] , lcs[i-1][j]) ;
}
}
cout<<lcs[n][n]<<endl ;
memset(lcs,0,sizeof(lcs)) ;
memset(b,0,sizeof(b)) ;

}

return 0 ;
}

sample input


sample output

1
2
3

UVA -10100 : Longest Match

//Problem link >>http://uva.onlinejudge.org/external/101/10100.html

/// in this LCS problem u may find it hard to manage a word ... here i've used file-stream I/O ... see the header file "sstream" & the command "stringstream" ... then uor string will be separated into words ... make sure u hide uor words in the form of a character ... here "check" array do this and then apply lcs to "check" array ...

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

int lcs[1002][1002] ,check [1002][1002] ;

int main ()
{
string s1 , s2 , s ;
int cas=0 ;
vector<string>v1 ;
vector<string>v2 ;

while (getline(cin,s1))
{
getline(cin,s2) ;
for (int i=0 ; i<s1.size() ; i++)
{
if (s1[i]>='a'&&s1[i]<='z' || s1[i]>='A' &&s1[i]<='Z' || s1[i]>='0'&&s1[i]<='9') continue ;
else s1[i]=' ' ;
}

for (int i=0 ; i<s2.size() ; i++)
{
if (s2[i]>='a'&&s2[i]<='z' || s2[i]>='A' &&s2[i]<='Z' || s2[i]>='0'&&s2[i]<='9') continue ;
else s2[i]=' ' ;
}

v1.clear() ;
v2.clear() ;

stringstream sx(s1) ;
stringstream sy(s2) ;

while(sx>>s) v1.push_back(s) ;
while(sy>>s) v2.push_back(s) ;

int x=v1.size() ;
int y=v2.size() ;

for (int i=0 ; i<x ; i++)
{
for (int j=0 ; j<y ; j++)
{
if (v1[i]==v2[j]) check[i][j]=1 ;
else check[i][j]=0 ;
}
}

for (int i=x ; i>=0 ; i--)
{
for (int j=y ; j>=0 ; j--)
{
if (i==x||j==y)
{
lcs[i][j]=0 ;
continue ;
}
if (check[i][j]==1) lcs[i][j]=1+lcs[i+1][j+1] ;
else lcs[i][j]=max(lcs[i+1][j],lcs[i][j+1]) ;
}
}

printf("%2d.",++cas) ;
if (x==0||y==0) cout<<" Blank!"<<endl ;
else cout<<" Length of longest match: "<<lcs[0][0]<<endl ;

}
return 0 ;
}

Sample Input

This is a test.
test
Hello!

The document provides late-breaking information
late breaking.

Sample Output

1. Length of longest match: 1
2. Blank!
3. Length of longest match: 2

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

UVA- 10066 : The Twin Towers

//Problem link >>http://uva.onlinejudge.org/external/100/10066.html

.. simple DP problem ... implementing straight LCS ....

#include <iostream>
#include <vector>
using namespace std ;
int main ()
{
int x , y ,a , b , cas=0 ;
int lcs[103][103] ;

vector<int>v1 ;
vector<int>v2 ;

while (cin>>x>>y && x||y)
{

v1.clear() ;
v2.clear() ;

for (int i=0 ; i<x ; i++)
{
cin>>a ;
v1.push_back(a) ;
}
for (int i=0 ; i<y ; i++)
{
cin>>a ;
v2.push_back(a) ;
}

for (int i=0 ; i<x ; i++) lcs[i][0]=0 ;
for (int i=0 ; i<y ; i++) lcs[0][i]=0 ;

for (int i=1 ; i<=x ; i++)
{
for (int j=1 ; j<=y ; j++)
{
if (v1[i-1]==v2[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<<"Twin Towers #"<<++cas<<endl ;
cout<<"Number of Tiles : "<<lcs[x][y]<<endl<<endl ;

}

return 0 ;
}

Sample Input

7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20

Sample Output

Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6

UVA- 10192 : Vacation

//Problem link >>http://uva.onlinejudge.org/external/101/10192.html

...DP problem ... LCS ...

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

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

int lcs(int i , int j)
{
if (i==x|| j==y) return 0 ;
int &bus=dp[i][j] ;

if (bus !=-1) return bus ;

if (s1[i]==s2[j]) return bus=1+lcs(i+1 , j+1) ;

return bus= max(lcs(i , j+1) , lcs(i+1 , j) ) ;

}

int main ()
{
int cas=0 ;
while (getline(cin,s1) && s1!="#")
{
getline(cin,s2) ;
x=s1.size() ;
y=s2.size() ;

memset(dp,-1,sizeof (dp)) ;

cout<<"Case #"<<++cas<<": ";
cout<<"you can visit at most "<<lcs(0,0)<<" cities."<<endl ;

}
return 0 ;
}

sample input::

abcd
acdb
abcd
dacb
#

sample output:

Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 2 cities.

Thursday, May 15, 2014