10405 - Longest Common Subsequence

[xlvector]

I will not paste functions I am not call next time.
Thank you for your hint

[WRJ]

Thank you!
I've had problem with reading input, too

[linhomeyeu]

WHY??

#include<stdio.h>
int main()
{
int aa,bb,i,j,k,h;
char a[1001],b[1001];
while(gets(a)!=NULL&&gets(b)!=NULL)
{
aa=strlen(a);bb=strlen(b);
for(i=0,k=0,h=-1;i<aa;i++)
for(j=h+1;j<bb;j++)
if(a==b[j])
{k++;h=j;break;}
printf("%d\n",k);
}
return 0;
}

[daveon]

Hi,

Your program fails on the following IO

Code: Select all

input:

cabc
abc

output:

3

[linhomeyeu]

thanks, but my code is still WR......Why?

Code: Select all

#include<stdio.h>
int main()
{
    int aa,bb,i,j,k,h;
    void reverse(char*a,char*b);
    char a[1001],b[1001];
    while(gets(a)!=NULL&&gets(b)!=NULL)
    {
    aa=strlen(a);bb=strlen(b);
    if(aa>bb)
        reverse(a,b);
    aa=strlen(a);bb=strlen(b);
        for(i=0,k=0,h=-1;i<aa;i++)
          for(j=h+1;j<bb;j++)
        	if(a[i]==b[j])
    	      {k++;h=j;break;}
    printf("%d\n",k);
    }
    return 0;
}

void reverse(char*a,char*b)
{
    int i,aa,bb;
    char c[1001];
    aa=strlen(a);bb=strlen(b);
    for(i=0;i<aa;i++)
        c[i]=a[i];
    c[i]=0;
    for(i=0;i<bb;i++)
        a[i]=b[i];
    a[i]=0;
    for(i=0;i<aa;i++)
        b[i]=c[i];
    b[i]=0;
}

[daveon]

Hi,

Your program fails the following:

Code: Select all

input:
abcxxxxxxxx
abxxxxxxxxc

output:
10

[linhomeyeu]

Sorry, Daveon. I'm still WR.

Code: Select all

code is deleted

[daveon]

Do you know of the DP solution to this Longest Common Subsequence problem?

If you just want to get AC, then you may look up this well known DP algorithm. However, if you are the one who likes to solve everything by yourself, then you'll have to prove that your algorithm is correct.

[linhomeyeu]

Do you know of the DP solution to this Longest Common Subsequence problem?

If you just want to get AC, then you may look up this well known DP algorithm. However, if you are the one who likes to solve everything by yourself, then you'll have to prove that your algorithm is correct.

I think I'm the second one. However, I have to thank for your forbearing answer.(I'm not a English-mother-language person, so my English may be awful. please do not care it.)

[darkos32]

hi,i dont use dp for this problems,i try to make another code,but why i got WA ?

Code: Select all

#include <stdio.h>
#include <string.h>
void main(){
	freopen("longest.in","r",stdin);
	freopen("longest.out","w",stdout);
	char a[1001] = "";char b[1001]="";
	while(gets(a)){
		gets(b);
		int ta = strlen(a);
		int tb = strlen(b);
		int max = 0;
		int i = 0;int j = 0;
		int tempi = ta;int tempj = tb;
		int maks = 0;
		while(i<ta){
			j = 0;
			while(j<tb){
				if(a[i]==b[j]){
					tempi = i+1;
					int tempjj = j+1;
					int byk = 1;
					//printf("%d %d - ",i,j);
					//printf("%c %c - ",a[i],b[j]);
					while(tempi<ta){
						tempj = tempjj;
						while(tempj<tb){
							if(a[tempi]==b[tempj]) {
								//printf("%d %d - ",tempi,tempj);
								//printf("%c %c - ",a[tempi],b[tempj]);
								byk++;
								tempjj=tempj+1;
								tempj+=tb;
							}
							tempj++;
						}
						//printf("%d - ",tempjj);
						tempi++;
					}
					//printf("\n");
					if(byk>maks) maks = byk;
				}
				j++;
			}
			i++;
		}
		printf("%d\n",maks);
	}
}

can anyone give me the testcase please ?
thanks.

[andysoft]

Hello World !
I have solved this problem (ok, AC) on C using usual LCS algo. My C prog ran during 1.807 sec and I am 2867 / 2899 in ranking. But I cannot understand how did some people solve this prob in 0.004 sec??! Even on Pascal, which is in most cases slower than C/C++! Any idea?

Thanx for attention

[emotional blind]

I don't know which one is faster? pascal or C?

But I know that bottom up approach is faster than top down approach, when you solve a DP problem.

My solution takes 0.027 sec.

[andysoft]

Okay, I will try to implement bottom up as you have said.
0.027 is believable, but how did people get 0.004 seconds? Can it be cheating (knowing I/O for the prob) ?

[emotional blind]

I just coded bottom up.. But didnt use any optimization in my code.
But a lot of optimization can be implemented.
Faster input output, faster calculation. I am not able to do all of that.

[andysoft]

Can you please make a hint for me to feel the difference between bottom up and top down in this problem. o(n^2) solution of this kind:

Code: Select all

for i in sequence 1
  for j in sequence 2
    if s1[i]=s2[j] then
      ans[i][j] = ans[i-1][j-1] + 1; 
    else if .... and so on ...

is top-down? or bottom-up?
thanx in advance