10405 - Longest Common Subsequence

[Ghost77 dimen]

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.

[SnapDragon]

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

[Hackson]

Should the output be
0
1
0
??

And I guess if the input is
aaaaab
aab

The output should be 3?

[liusu]

why WA?can anyone help me?

[Larry]

Make sure you handle all characters?

[Haomiao]

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

[Dominik Michniewski]

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

Regards
Dominik

[Haomiao]

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

[htl]

The input may contain spaces.

[Dominik Michniewski]

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

Dominik

[mido]

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]

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]

what about this test input

Code: Select all

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




[justforfun]

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]