10405 - Longest Common Subsequence

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja »

Use this algorithm. I think that it's a simple and clear LCS( Longest
Common Sequence) algorithm pseudocode.

[cpp]
LCS-Length(X,Y)
m <- length[X]
n <- length[Y]

for i = 1 to m
do c[i,0] <- 0
for j = 0 to n
do c[0,j] <- 0
for i = 1 to m
do for j = 1 to n
do if x = y[j]
then c[i,j] <- c[i-1, j-1] + 1
else if c[i-1,j] >= c[i,j-1]
then c[j] <- c[i-1,j]
else c[i,j] <- c[i,j-1]
return c and b

[/cpp]

If you have the book "Introduction to algorithm
( MIT Press, second edition )", then you can see more detail explain.
( from chapter 13.4 Longest common sequence )[/cpp]

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

the same process is in the book of crls...
it's very easy i think that the 1st one...
thanks...
--
anupam :oops: :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido »

Thanks guys...I got to find out what LCS is all about; this problem is a textbookexample for this type of algorithm...thanks again...:)

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung »

I notice my solution is way way "too slow" compared to others'. Mine runs in 0.125 sec while the fastest ones are like around 0.010. What causes my program to be so slow? Or do others simply add some optimization tricks I wasn't aware of?



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

int main()
{
string shorter, longer, temp1;
int lenShorter, lenLonger, temp2;
while(true)
{
getline(cin, shorter);
getline(cin, longer);
if(cin.eof())
break;
lenShorter = shorter.length();
lenLonger = longer.length();
if(lenShorter == 0 || lenLonger == 0)
{
cout << "0\n";
continue;
}

int lcs[lenShorter+1][lenLonger+1];

for(int i=0; i<=lenShorter; i++)
lcs[0] = 0;
for(int j=0; j<=lenLonger; j++)
lcs[0][j] = 0;

for(int i=1; i<=lenShorter; i++)
{
for(int j=1; j<=lenLonger; j++)
{
if(shorter[i-1] == longer[j-1])
lcs[j] = lcs[i-1][j-1] + 1;
else if(lcs[i-1][j] >= lcs[j-1])
lcs[j] = lcs[i-1][j];
else lcs[j] = lcs[j-1];
}
}
cout << lcs[lenShorter][lenLonger] << "\n";
}
return 0;
}[/cpp]

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10405

Post by Eduard »

Help please i don't know why i'm geting WA.my algoritm is rigth i know i thing i'm doing something wrong whith the input help please.
Thanks.
[pascal]program hachortakanutjun;
const m=1000;
var x,y,Z:array[1..1000] of char;
a:array[0..m,0..m] of byte;
i,nx,ny,j,k:integer;
begin
while not eof do
begin
nx:=0;
repeat
nx:=nx+1;
read(x[nx]);
until ord(x[nx])=10;
ny:=0;
repeat
ny:=ny+1;
read(Y[ny]);
until ord(y[ny])=10;
nx:=nx-2;
ny:=ny-2;
for i:=1 to ny do
for j:=1 to nx do
if X[j]=Y then a[i,j]:=a[i-1,j-1]+1
else if a[i-1,j]>a[i,j-1] then a[i,j]:=a[i-1,j] else a[i,j]:=a[i,j-1];
writeln(a[ny,nx]);
end;
end.
[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

Hi Eduard,

I am not quite familiar with PASCAL, but there can be space characters in the string.

What is your output for the following cases:

aaaaaaaaaaaaa
aaaa
dfsafjasdfs
asdfasdfasf
12345
54321

:-?

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

5
8
2

this are my answers.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

The correct solution to the above 3 inputs are:

Code: Select all

4
7
1
I don't know Pascal, but it's possible you're considering the newline at the end of the lines too [which would explain the +1 offset].

That, or you copied the extra space into the input file.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

there is space after word when i copy it to filr i saw it that why my program give 5 8 2 not 4 7 1
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

And there could be a blank lines, in that case the answer will be zero.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

Thank All of You I finnaly get ACCEPTED
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

babu_nothing
New poster
Posts: 2
Joined: Mon May 31, 2004 2:36 am

10405-why W.A

Post by babu_nothing »

Ca any one help me.?? I don't know why I gotta W.A.........[cpp]

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

char s1[1009],s2[1009];
int m,n,i,j,M[1100][1100];

void Process()
{
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(s1[i-1]==s2[j-1])
M[j]=M[i-1][j-1]+1;
else if(M[i-1][j]>M[j-1])
M[j]=M[i-1][j];
else
M[j]=M[j-1];

}

void main()
{
memset(s2,'\0',sizeof(s2));
memset(s2,'\0',sizeof(s2));

while(scanf("%s%s",&s1,&s2)==2)
{
memset(M,0,sizeof(M));
m=strlen(s1);
n=strlen(s2);
Process();
printf("%d\n",M[m][n]);
memset(s2,'\0',sizeof(s2));
memset(s2,'\0',sizeof(s2));

}
}[/cpp]

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 »

Hi babu_nothing,

The input can contain empty strings.
Change scanf() into gets(), and you will get AC. :wink:

Code: Select all

while(gets(s1))
   {
      gets(s2);
      ...
   }

Anggakusuma

babu_nothing
New poster
Posts: 2
Joined: Mon May 31, 2004 2:36 am

Post by babu_nothing »

thanks for Ur help, i get AC.....

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm

Post by paulidirac »

hi the following is my code (in c++)...but i get WA...

Code: Select all

#include <iostream.h>
#include <string.h>

void main(void)
{
	char a[1002], b[1002];
	int pos[1002],best[1002],loc[1002];
	int i,j,k,l,alen,blen,max,temp,last;
	while(1){  	
		cin>>a;
		if (cin.eof()) break;
		cin>>b;

		alen=strlen(a);
		blen=strlen(b);
		pos[0]=0;

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

		max=0;
		for (i=0;i<pos[blen];i++)
			if (max<best[i])	max=best[i];
		cout << max << endl;
	}
}
i think the problem is with my way of reading input cos i ran a lot of test cases and my algo seems fine...

Post Reply

Return to “Volume 104 (10400-10499)”