## 10405 - Longest Common Subsequence

Moderator: Board moderators

Thanks Larry I got AC
sklitzz
New poster

Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### 10405 WA!

What's wrong?
Code: Select all
`#include <stdio.h>#include <string.h>#define LEN 100int m,n,i,j;char c[LEN][LEN],b[LEN][LEN];int ans;char X[LEN],Y[LEN];int LCS_length(){m=strlen(X);n=strlen(Y);for(i=1;i<=m;i++) c[i][0]=0;for(j=0;j<=n;j++) c[0][j]=0;for (i=1;i<=m;i++)  for (j=1;j<=n;j++) {      if(X[i]==Y[j]) {         c[i][j]=c[i-1][j-1]+1;         b[i][j]= 1;         }      else if(c[i-1][j]>=c[i][j-1]) {         c[i][j] = c[i-1][j];         b[i][j]=2;         }      else{         c[i][j]=c[i][j-1];         b[i][j]=3;         }      }return c[m][n];}void main(){while(1) {gets(X);if (feof(stdin)) break;gets(Y);ans = LCS_length();printf("%d\n",ans);}}`
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

String lengths can be as much as 1000.

Regards
Sanny
Sanny
Learning poster

Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET

Why do you need the b[][] array ? The problem does not ask you to print LCS, just print the length of the LCS.
Raiyan Kamal
Experienced poster

Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm

### 10405 - Longest Common Subsequence

hi all...

i have submitted my code...

but! why WA ???

i dont really know the reason.. who anyone help me please...

the code is very simple LCS...

Code: Select all
`#include <stdio.h>#include <string.h>void main(void){   char str1[1010], str2[1010];   int len1, len2;   int i, j;   char map[1010][1010];   while ( 1 )    {      if ( gets(str1) == NULL )          break;      if ( gets(str2) == NULL )          break;      len1 = strlen(str1);      len2 = strlen(str2);      for ( i = 0 ; i <= len1 ; i++ )          map[i][0] = 0;      for ( i = 0 ; i <= len2 ; i++ )          map[0][i] = 0;      for ( i = 1 ; i <= len1 ; i++ )          for ( j = 1 ; j <= len2 ; j++ )             if ( str1[i-1] == str2[j-1] )             {               map[i][j] = map[i-1][j-1] + 1;            }            else if ( map[i-1][j] >= map[i][j-1] )             {               map[i][j] = map[i-1][j];            }            else            {               map[i][j] = map[i][j-1];            }      printf("%d\n", map[len1][len2]);   }   }`
pipo
New poster

Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

### out of limit...

since the strings can be as many as 1000 characters it implies the result could have a value of 1000..

.. so, char map[1010][1010] won't work.

try converting the data type to integer.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

sohel!! thank you very much...

you're right...

i didn't think about that point...

I just converted the data type to integer... and then I finally got AC..

thanks a lot ...
pipo
New poster

Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

### 10405, WA, plz HELP!!!

getting WA...
here is my code...
//10405 - Longest Common Subsequence

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

char b[1001][1001],c[1001][1001];
char x[1005],y[1005];

void lcs(int m,int n)
{
int i,j;

for(i=1;i<m+1;i++){
c[i][0]=0;
b[i][0]=' ';
}
for(j=0;j<m+1;j++){
c[0][j]=0;
b[0][j]=' ';
}

for(i=1;i<m+1;i++){
for(j=1;j<n+1;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]='C';
}
else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]='U';
}
else{
c[i][j]=c[i][j-1];
b[i][j]='L';
}
}
}
}

void main()
{
int m,n;

//freopen("E:\\test.txt","rt",stdin);

while(gets(&x[1]) != NULL && gets(&y[1]) != NULL){
m = strlen(&x[1]);
n = strlen(&y[1]);

lcs(m,n);

printf("%d\n",c[m][n]);
}
}
Darkness be my guide...
Darken
New poster

Posts: 2
Joined: Thu Sep 08, 2005 8:08 pm

### hello

hello
here is an ACC soln
Code: Select all
`#include <stdio.h>#include <string.h>const int MAX = 1005;char x[MAX]={'a'}, y[MAX]={'a'};int c[MAX][MAX];void LCS_Length(){   int m = strlen(x)-1, n = strlen(y)-1, i,j;   for(i = 1; i<=m; i++) c[i][0] = 0;   for(j = 0; j<=n; j++) c[0][j] = 0;   for(i = 1; i<=m; i++){      for(j = 1; j<=n; j++){         if( x[i] == y[j] ){            c[i][j] = c[i-1][j-1] + 1;         }         else if( c[i-1][j] >= c[i][j-1] ){            c[i][j] = c[i-1][j];         }         else            c[i][j] = c[i][j-1];      }   }   printf("%d\n", c[m][n]);}void main(void){   //freopen("f:\\10405.txt","rb",stdin);   while( gets(x+1)&& gets(y+1) ){      LCS_Length();   }}`

it's simple...
isn't it???????

again...
USE proper formet while posting code.
ur's is not better readable, let alone to bebug.
and i will remove the code as u reply me..
bye!!!!
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.
I LIKE GN
Learning poster

Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC

### Re: 10405, WA, plz HELP!!!

Darken wrote:
Code: Select all
`   for(i=1;i<m+1;i++){      c[i][0]=0;      b[i][0]=' ';   }   for(j=0;j<m+1;j++){      c[0][j]=0;      b[0][j]=' ';   }`

There should be n+1 in the second for loop.

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Thanx...

it was not the problem... I didn't take the inputs for a blank line... any way finally i have got acceptance:P . thanx for ur care. take care. bye.
Darkness be my guide...
Darken
New poster

Posts: 2
Joined: Thu Sep 08, 2005 8:08 pm

### 10405 WA,help

I use dynamic programming, but I still get WA, can someone help me.

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

#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)>(b)?(a):(b))

class LCSLength
{
public:
LCSLength(){}
string solve(string A, string B);
int length(string A, string B);
};

int LCSLength::length(string A, string B)
{
if(A.size()==0 || B.size()==0) return 0;
int m = A.size()+1;
int n = B.size()+1;
int* c = new int[m*n];
memset(c,0,m*n*sizeof(int));
c[0] = 0;
int i,j;
for(i=1;i<m;i++){
for(j=1;j<n;j++){
if(A[i-1] == B[j-1]){
c[i*n+j] = c[(i-1)*n+(j-1)]+1;
}else{
c[i*n+j] = MAX(c[i*n+j-1],c[(i-1)*n+j]);
}
//cout<<c[i*n+j]<<" ";
}
//cout<<endl;
}
int ret = c[m*n-1];
delete[] c;
return ret;
}

string LCSLength::solve(string A, string B)
{
int M = A.size();
int N = B.size();
if(M==0 || N==0) return "";
string *str = new string[M*N];
if(A[0] == B[0]) str[0] = A[0];
else str[0] = "";
int i,j;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(i==0 && j==0) continue;
if(A[i] == B[j]){
if(i==0 || j==0){
str[i*N+j] = A[i];
}else{
str[i*N+j] = str[(i-1)*N+(j-1)] + A[i];
}
//cout<<str[i*N+j]<<endl;
}
else{
if(i==0){ str[i*N+j] = str[i*N+j-1]; continue; }
if(j==0){ str[i*N+j] = str[(i-1)*N+j]; continue; }
if(str[(i-1)*N+j].size() >= str[i*N+j-1].size())
str[i*N+j] = str[(i-1)*N+j];
else str[i*N+j] = str[i*N+j-1];
}

}
}
return str[M*N-1];
}

int main()
{
string A,B;
LCSLength LCS;
while(cin>>A>>B){
cout<<LCS.length(A,B)<<endl;
}
return 0;
}[/code]
xlvector
New poster

Posts: 11
Joined: Thu Dec 29, 2005 8:30 am

What's the difference between your MAX and MIN macros?
mamun
A great helper

Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm

### Sorry, I make a mistake

But I only use MAX in program
xlvector
New poster

Posts: 11
Joined: Thu Dec 29, 2005 8:30 am

Try taking the input with gets() or similar functions. I think there can be whitespaces within the strings. Otherwise the class LCSLength seems ok.

And please, next time u post codes in the board, try removing unnecessary portions of the code. This will save time of people who are trying to help you. You have a complete function in your code which is never called , let alone a single macro .
Where's the "Any" key?
Solaris
Learning poster

Posts: 99
Joined: Sun Apr 06, 2003 5:53 am