10405 - Longest Common Subsequence

[sklitzz]

Thanks Larry I got AC

[smilitude]

What's wrong?

Code: Select all

#include <stdio.h>
#include <string.h>
#define LEN 100

int 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);
}
}


[Sanny]

String lengths can be as much as 1000.

Regards
Sanny

[Raiyan Kamal]

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

[pipo]

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]);
   }   
}


[sohel]

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.

[pipo]

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 ...

[Darken]

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]);
}
}

[I LIKE GN]

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!!!!

[Martin Macko]

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.

[Darken]

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.

[xlvector]

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]

[mamun]

What's the difference between your MAX and MIN macros?

[xlvector]

But I only use MAX in program

[Solaris]

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 .