10405 - Longest Common Subsequence

[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]

the same process is in the book of crls...
it's very easy i think that the 1st one...
thanks...
--
anupam

[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]

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]

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]

[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]

5
8
2

this are my answers.

[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]

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

[shamim]

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

[Eduard]

Thank All of You I finnaly get ACCEPTED

[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]

Hi babu_nothing,

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

Code: Select all

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

Anggakusuma

[babu_nothing]

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

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