10405 - Longest Common Subsequence

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

Moderator: Board moderators

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

10405 - Longest Common Subsequence

Post by Ghost77 dimen » Mon Nov 11, 2002 8:05 pm

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

Post by SnapDragon » Tue Nov 12, 2002 2:06 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

reply

Post by Hackson » Tue Nov 12, 2002 3:44 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?

Post by liusu » Sat Nov 16, 2002 8:42 am

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:

Post by Larry » Sat Nov 16, 2002 10:12 am

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

Post by Haomiao » Tue Nov 19, 2002 11:33 am

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

Post by Dominik Michniewski » Tue Nov 19, 2002 12:44 pm

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

Post by Haomiao » Tue Nov 19, 2002 2:52 pm

:( i've known the answer about it.
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

Post by htl » Wed Nov 20, 2002 1:04 am

The input may contain spaces.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Nov 20, 2002 9:08 am

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

Post by mido » Sun Feb 16, 2003 2:21 pm

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

Post by Nick » Fri Feb 21, 2003 6:34 am

can anyone tell me some test input and the correct output?
what's the output of

Code: Select all

abckkkbbbcccbbbddd
abbbcccd

?fiweuhvnwjs
27hwnfguhewru43?

please help



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

Post by Nick » Fri Feb 21, 2003 6:56 am

what about this test input

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

Post by justforfun » Sun Feb 23, 2003 7:38 pm

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

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

Post by Nick » Mon Feb 24, 2003 4:20 am


Post Reply

Return to “Volume 104 (10400-10499)”