10405 - Longest Common Subsequence
Moderator: Board moderators
-
- 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]
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]
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]
[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]
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;
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]
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
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
5
8
2
this are my answers.
8
2
this are my answers.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
The correct solution to the above 3 inputs are:
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.
Code: Select all
4
7
1
That, or you copied the extra space into the input file.
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
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Thank All of You I finnaly get ACCEPTED
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
-
- 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[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]
#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]
Hi babu_nothing,
The input can contain empty strings.
Change scanf() into gets(), and you will get AC.
Anggakusuma
The input can contain empty strings.
Change scanf() into gets(), and you will get AC.
![:wink:](./images/smilies/icon_wink.gif)
Code: Select all
while(gets(s1))
{
gets(s2);
...
}
Anggakusuma
-
- New poster
- Posts: 2
- Joined: Mon May 31, 2004 2:36 am
-
- New poster
- Posts: 5
- Joined: Mon Jun 07, 2004 9:00 pm
hi the following is my code (in c++)...but i get WA...
i think the problem is with my way of reading input cos i ran a lot of test cases and my algo seems fine...
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;
}
}