Page 2 of 7
Posted: Mon Apr 07, 2003 4:27 am
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]
Posted: Thu Apr 10, 2003 1:33 am
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...
Posted: Fri Jun 13, 2003 9:46 pm
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]
10405
Posted: Wed Dec 24, 2003 10:36 am
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]
Posted: Wed Dec 24, 2003 2:04 pm
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
Posted: Wed Dec 24, 2003 9:43 pm
by Eduard
5
8
2
this are my answers.
Posted: Wed Dec 24, 2003 10:46 pm
by UFP2161
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.
Posted: Thu Dec 25, 2003 4:42 pm
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
Posted: Sat Dec 27, 2003 7:59 am
by shamim
And there could be a blank lines, in that case the answer will be zero.
Posted: Sun Dec 28, 2003 12:56 pm
by Eduard
Thank All of You I finnaly get ACCEPTED
10405-why W.A
Posted: Thu Jun 03, 2004 1:03 am
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]
Posted: Thu Jun 03, 2004 7:02 am
by angga888
Hi babu_nothing,
The input can contain empty strings.
Change scanf() into gets(), and you will get AC.
Anggakusuma
Posted: Thu Jun 03, 2004 2:59 pm
by babu_nothing
thanks for Ur help, i get AC.....
Posted: Mon Jun 07, 2004 9:09 pm
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...
