## 10405 - Longest Common Subsequence

Moderator: Board moderators

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### 10405 - Longest Common Subsequence

some my test input
------>only contain '\n'
------>only contain '\n'
------>contain one space and '\n'
------>contain two spaces and '\n'
123
321
abba
bbaa
output
0
1
1
3
Is anthing wrong?
At first , my solution is not consider space and it is wrong.
Last edited by Ghost77 dimen on Tue Nov 12, 2002 4:10 am, edited 1 time in total.

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am
Try the following input:
a
(blank line)
a
a
a
(blank line)

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Should the output be
0
1
0
??

And I guess if the input is
aaaaab
aab

The output should be 3?

liusu
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

### why WA?

why WA?can anyone help me?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Make sure you handle all characters?

Haomiao
New poster
Posts: 5
Joined: Sat Nov 16, 2002 11:28 am
Location: Xi'an,China
Contact:

### 10405:who can tell me why?wrong answer...impossible....

[cpp]
{
while(infile>>a>>b)
{
outfile<<maxCommonString()<<endl;
}
}

int maxCommonString()
{
int i,j;
int m=a.size();
int n=b.size();
for(i=0;i<up;i++)
for(j=0;j<up;j++)
c[j]=0;
for(int i=1;i<=m;i++)
c[0]=0;
for(int i=1;i<=n;i++)
c[0]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if (a[i-1]==b[j-1])
c[j]=c[i-1][j-1]+1;
else
if (c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];
else
c[j]=c[j-1];
}

return c[m][n];

}
[/cpp]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
LCS function looks good .... (same as mine )
I guess, that you have problem with reading input ....

Regards
Dominik

Haomiao
New poster
Posts: 5
Joined: Sat Nov 16, 2002 11:28 am
Location: Xi'an,China
Contact:

### if a string has nothing....

i've never thought about the condition of a string null....

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
The input may contain spaces.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
... and the best method to read input is use gets() or something like gets() in c++ )

Dominik

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

### 10405 again

What's wrong with this...:
[cpp]#include <iostream.h>
#include <string.h>

void main()
{
char* str=new char[1100];
char* str2=new char[1100];
while (!cin.eof())
{
/*char ch;
while (cin.get(ch) && (ch==' '))
{}
if (cin.eof())
break;
cin.putback(ch);

ch=0;
while (cin.get(ch) && (ch==' '))
{}
cin.putback(ch);*/
cin.getline(str,1100,'\n');
cin.getline(str2,1100,'\n');
int max=0;
int i,j,count;
int len=strlen(str);
int len2=strlen(str2);
for (i=0;i<len;i++)
{
j=0;
count=0;
int pivot1=i;
int pivot2=0;
while (pivot1<len)
{
j=pivot2;
while (j<len2 && str2[j]!=str[pivot1])
j++;
if (j<len2)
{
j++;
count++;
pivot1++;
pivot2=j;
}
else
{
pivot1++;
j=pivot2;
}
}
if (count>max)
max=count;
}
cout<<max<<endl;
}
}

[/cpp]

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am
can anyone tell me some test input and the correct output?
what's the output of

Code: Select all

``````abckkkbbbcccbbbddd
abbbcccd

?fiweuhvnwjs
27hwnfguhewru43?

``````

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Code: Select all

``````aabcccddd
abdddcccddd
aabccccdddcccddd
abcccddd
??? jake
jak?e??
crajudzyge
crazyjudge
hehehehe :)
eheheheh ):

``````

justforfun
New poster
Posts: 5
Joined: Sun Feb 23, 2003 7:33 pm

### WAWAWA!!!

I've tried all test data i can find..
but still got a WA!
can anyone take a look on my code?

Code: Select all

``````[color=blue][/color]
#include<stdio.h>
#include<string.h>
int main()
{
int length1,length2,i,j,k;
char temp,arr1[1001],arr2[1001];
while (gets(arr1))
{
int max=0,count,temp;
gets(arr2);
length1=strlen(arr1);
length2=strlen(arr2);
for (i=0;i<length1;i++)
{
count=0;
temp=0;
for (j=i;j<length1;j++)
{
for (k=temp;k<length2;k++)
{
if (arr1[j]==arr2[k])
{
count++;
temp=k+1;
break;
}
}
}
if (count>max)
max=count;
}
printf("%d\n",max);
}
}``````

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am