## 10405 - Longest Common Subsequence

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
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:
the same process is in the book of crls...
it's very easy i think that the 1st one...
thanks...
--
anupam    "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
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:
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;
for(int j=0; j<=lenLonger; j++)
lcs[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

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;
until ord(x[nx])=10;
ny:=0;
repeat
ny:=ny+1;
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
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
5
8
2

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

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

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

char s1,s2;
int m,n,i,j,M;

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
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
New poster
Posts: 2
Joined: Mon May 31, 2004 2:36 am
thanks for Ur help, i get AC.....

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm
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, b;
int pos,best,loc;
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;

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