10405 - Longest Common Subsequence

[angga888]

hi,

i think the problem is with my way of reading input cos i ran a lot of test cases and my algo seems fine...

Have you consider about empty lines?

Input :

Code: Select all

a


a

Output :

Code: Select all

0
0

I think your program can't handle such cases.

Hope it helps


Anggakusuma

[paulidirac]

i tried with gets instead of cin...it can handle null strings...i also submit my program as C instead of C++...but now i get Runtime Error (SIGSEGV) after 0.316 seconds of execution.... wat's the error supposed to mean? thanx

[angga888]

Hi,

i tried with gets instead of cin...it can handle null strings...i also submit my program as C instead of C++...but now i get Runtime Error (SIGSEGV) after 0.316 seconds of execution.... wat's the error supposed to mean? thanx

I'm suspicious with this fragment:

Code: Select all

for (i=0;i<blen;i++){ 
   last=pos[i]; 
   for (j=0;j<alen;j++){ 
      if (a[j]==b[i]){ 
         max=0; 
         for (k=i-1;k>=0;k--){ 
            for (l=pos[k];l<pos[k+1];l++){ 
               if (loc[l]<j && max<best[l]){ 
                  max=best[l]; 
               } 
            } 
         } 
         best[last]=max+1; 
         loc[last]=j; 
         last++; 
     } 
   } 
   pos[i+1]=last; 
}

Consider input:

Code: Select all

aaaa...(repeated 1000 times)
aaaa...(also repeated 1000 times)

Your program will work as follows:
- in the first step (i=0) -> last=0 , then j will be repeated 1000 times, and last will become 0+1000.
- next step (i=1) -> last=1000, and then j will be repeated 1000 times, and last will become 1000+1000.

In this situation, last will be greater than 1000, and will also exceed your maximum array bound (1002). This will cause runtime error.

Hope it helps


Anggakusuma

[emka]

Hi

Can anybody figure out the bugs within my code?
I got WA for this. Thanks

[cpp]
#include <iostream>
#include <string.h>

using namespace std;

int main(void){
int ar[2][1001], top = 1, bottom = 0;
char s1[1001], s2[1001];

while ( cin ){
cin.getline( s1, 1001 );
cin.getline( s2, 1001 );

//----------------------------------------------
//--------- code segment removed ---------------
//----------------------------------------------

}

return 0;
}[/cpp]

[paulidirac]

hi,
thanx for the help...i thought i'd be saving on mem that way, but guess i couldn't..but it's very surprising that even after allocating a 1000 X 1000 array at compile time, the judge shows that my code runs in 64k.. is there some flaw in the judge memory monitoring?
thanx.

[angga888]

it's very surprising that even after allocating a 1000 X 1000 array at compile time, the judge shows that my code runs in 64k..

I don't know either. If your program runs fast, usually the memory will become only 64k.

[angga888]

You can change the way you read the input:
[cpp]while ( cin.getline( s1, 1001) ){
cin.getline( s2, 1001 );
...
}[/cpp]
Hope it helps

[emka]

Well done, got AC now!

Thanks a lot

[[senu]]

What causes my program to be so slow? Or do others simply add some optimization tricks I wasn't aware of?

[cpp]#include <iostream>
#include <string>
[/cpp]

i like STL, but vectors/streams/strings etc are slower than pointers/printf/scanf/char *

[[senu]]

i got WA, but im sure my solution is good. can You help me?

[cpp]#include <stdio.h>
#include <iostream>
#define MAX 1002
#define f(x)for(int i=0; i<=x; i++)
#define f2(x,y)for(int i=x; i<=y; i++)

using namespace std;

int i,k,j,l,m,n,qq,c,maxc;
int t[MAX+1][MAX+1];
char a[MAX], b[MAX];

int max(int a, int b){if(a>=b)return a; else return b;}

int lcs(char *A, char *B)
{
f(m) t[n+1]=0;
f(n) t[m+1]=0;
t[0][0]=0;

for(int i=m; i>=0; i--)
for(int j=n; j>=0; j--)
{
if(a=='\0' || b[j]=='\0') t[j]=0;
else if (a==b[j]) t[j]=t[i+1][j+1]+1;
else t[j]=max(t[i+1][j],t[j+1]);
}

return t[0][0];
}

int main()
{
while ( cin.getline( a, 1001) )
{
cin.getline( b, 1001 );

i=0; while (a!='\n' && a!='\0') i++; m=--i;
i=0; while (b[i]!='\n' && b[i]!='\0') i++; n=--i;

cout << lcs(a,b) << endl;
}


return 0;
}
[/cpp]

[[senu]]

[cpp] --m=strlen(a);
--n=strlen(b);
[/cpp]

OK. I got AC, but i dont know why :PPP
Can You tell me?

[jackie]

I use DP LCS algorithm and got AC.
here it's input and output hope it can help those who get WA

[cpp] while (gets(d1))
{
gets(d2);
m = strlen(d1);
n = strlen(d2);
if (m == 0 || n == 0)
break;
// do the LCS
printf("%d\n", lcs[m][n]);
}[/cpp]

[thincal]

[cpp]
#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
char a[1001],b[1001];
int L[1001][1001];

int main(){
int la,lb,i,j;
while(gets(a) && gets(b)){
la=strlen(a),lb=strlen(b);
for(i=la;i>=1;i--)a=a[i-1];
for(i=lb;i>=1;i--)b=b[i-1];
memset(L,0,sizeof(L));
for(i=1;i<=la;i++)
for(j=1;j<=lb;j++){
if(a==b[j])L[j]=L[i-1][j-1]+1;
else L[j]=max(L[i-1][j],L[j-1]);
}
cout<<L[la][lb]<<endl;
}
return 0;
}[/cpp]

[sklitzz]

I don't get, why do I get WA?

Code: Select all

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

#define MAX 1001

int lcs( char *s1, char *s2 )
{
	int i, j;
	int dp[MAX][MAX] = { 0 };
	int len1 = strlen( s1 ), len2 = strlen( s2 );
	
	for( i = 1; i <= len1; ++i )
		for( j = 1; j <= len2; ++j )
			if( s1[i-1] == s2[j-1] ) dp[i][j] = dp[i-1][j-1] + 1;
			else if( dp[i-1][j] >= dp[i][j-1] ) dp[i][j] = dp[i-1][j];
			else dp[i][j] = dp[i][j-1];
	return dp[len1][len2];
}

int main()
{
	char s1[MAX], s2[MAX];
	while( ( scanf( "%s", s1 ) !=EOF ) && ( scanf( "%s", s2 ) != EOF ) )
		printf( "%d\n", lcs( s1, s2 ) );
	return 0;
}

[Larry]

You should read them line by line instead. I think there might be spaces.. (don't remember.)

Try:

Code: Select all

while ( gets( s1 ) && gets( s2 ) )

instead..