## 10405 - Longest Common Subsequence

All about problems in Volume CIV. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Ghost77 dimen
Learning poster

Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Try the following input:
a
(blank line)
a
a
a
(blank line)
SnapDragon
Problemsetter

Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

### reply

Should the output be
0
1
0
??

And I guess if the input is
aaaaab
aab

The output should be 3?
Hackson
New poster

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

### why WA?

why WA?can anyone help me?
liusu
New poster

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

Make sure you handle all characters?
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

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

[cpp]
void readData()
{
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[i][j]=0;
for(int i=1;i<=m;i++)
c[i][0]=0;
for(int i=1;i<=n;i++)
c[0][i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else
if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}

return c[m][n];

}
[/cpp]
Haomiao
New poster

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

LCS function looks good .... (same as mine )
I guess, that you have problem with reading input ....

Regards
Dominik
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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

i've known the answer about it.
i've never thought about the condition of a string null....
Haomiao
New poster

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

The input may contain spaces.
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

... and the best method to read input is use gets() or something like gets() in c++ )

Dominik
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### 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]
mido
Learning poster

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

can anyone tell me some test input and the correct output?
what's the output of
Code: Select all
`abckkkbbbcccbbbdddabbbcccd?fiweuhvnwjs27hwnfguhewru43?please help`
Nick
Learning poster

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

what about this test input
Code: Select all
`aabcccdddabdddcccdddaabccccdddcccdddabcccddd ??? jakejak?e??crajudzygecrazyjudgehehehehe :)eheheheh ):`
Nick
Learning poster

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

### 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);    }}`
justforfun
New poster

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

Nick
Learning poster

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

Next

Return to Volume CIV

### Who is online

Users browsing this forum: No registered users and 1 guest