10100 - Longest Match

[danielrocha]

INPUT:
what the hell
is going on

OUTPUT:
1. Length of longest match: 0

Daniel "Naz

[danielrocha]

Input:

Code: Select all

12 12
12 12
this is a test
this is is a a test
76.67 67
67 67 76



asd

 
    
    
a s d c f 
a d c
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
a s d
r t g
.;.;[
.;.;[

Output:

Code: Select all

 1. Length of longest match: 2
 2. Length of longest match: 4
 3. Length of longest match: 2
 4. Blank!
 5. Blank!
 6. Blank!
 7. Length of longest match: 0
 8. Length of longest match: 3
 9. Length of longest match: 11
10. Length of longest match: 0
11. Length of longest match: 0

The "Blank!" test should be "if (strlen(string)==0 || strlen(string2)==0)". Otherwise, I just replaced all non-alphanumeric caracters with a space and used strtok.

[TISARKER]

Here is my code can any one tell why it gives wrong answer ?
#include<stdio.h>
#include<string.h>
#define range 1000
#define dtype char
int lcs_len(int dp[range+1][range+1],int path[range+1][range+1],dtype a[range][21],dtype b[range][21],int n1,int n2);
int load(char data[range][21],char s[21],int len);
int dp[range+1][range+1];
int total=1;
void main()
{
//clrscr();
int n1,n2;
char a[range][21],b[range][21],s1[21],s2[21];
while(gets(s1))
{
gets(s2); n1=strlen(s1); n2=strlen(s2);
printf("%2d. ",total);
if((n1==0)||(n2==0))printf("Blank!\n");
else
{
n1=load(a,s1,n1); n2=load(b,s2,n2);
printf("Length of longest match: %d\n",lcs_len(dp,dp,a,b,n1,n2));
}
total++;
}
}

int load(char data[range][21],char s[21],int len)
{
int i,count=0,pos=-1;strcat(s," "); len++;
for(i=0;i<len;i++)
if(((s[i]>64)&&(s[i]<91))||((s[i]>96)&&(s[i]<123))||((s[i]>47)&&(s[i]<58)))
{
if(pos==-1)pos=i;
}
else if(pos!=-1)
{
s[i]=0;strcpy(&data[count][0],s+pos); pos=-1; count++;
}
return count;
}

int lcs_len(int dp[range+1][range+1],int path[range+1][range+1],dtype a[range][21],dtype b[range][21],int n1,int n2)
{
int i,j; n1++; n2++;
for(i=0;i<n1;i++){dp[0][i]=0;dp[i][0]=0;path[0][i]=0;path[i][0]=0;}
n1--;n2--;
for(i=0;i<n1;i++)
for(j=0;j<n2;j++)
if(strcmp(&a[i][0],&b[j][0])==0)
{
path[i+1][j+1]=1;
dp[i+1][j+1]=dp[i][j]+1;
}
else if(dp[i+1][j]>=dp[i][j+1])
{
path[i+1][j+1]=2;
dp[i+1][j+1]=dp[i+1][j];
}
else
{
path[i+1][j+1]=3;
dp[i+1][j+1]=dp[i][j+1];
}
return dp[n1][n2];
}

[Ali Arman Tamal]

I am getting WA from the judge, don't know why

The problem description is very unclear, it says:

Blank lines and non-letter printable punctuation characters may appear.

What do they mead by "non-letter printable punctuation characters". I have only considered A-Z and a-z and 0-9 as characters in the word and any other character equivalent to whitespace. Is it correct ?

If anybody can tell me which are the "non-letter printable punctuation characters", I will be very greatful. I am totally puzzled here .

Here is my code: [ plz if you find any error tell me ]

Code: Select all

#include <stdio.h>
#include <string.h>

int strcount1=0,strcount2=0,casecount=0;

struct data
{
char str[20];
};                

struct data a[600],b[600];

char x[1001],y[1001];

int d[600][600];



void makelist_1()
{

int i=0,j=0,k=0,flag=0;

	while(x[i]!='\0')
	{

	if((x[i]>='A' && x[i]<='Z')||(x[i]>='a' && x[i]<='z') || 
 (x[i]>='0' && x[i]<='9'))

	{
		flag=1;
		a[k].str[j]=x[i];
		j++;

	}


	else if(flag==1){ 
                a[k].str[j]='\0'; 
                k++; 
                j=0; 
                flag=0; 
                }

	i++;
	}

if(flag==1){ 
a[k].str[j]='\0'; 
k++; 
}

strcount1=k;

}



void makelist_2()
{

int i=0,j=0,k=0,flag=0;

	while(y[i]!='\0')
	{

	if((y[i]>='A' && y[i]<='Z')||(y[i]>='a' && y[i]<='z') || 
 (y[i]>='0' && y[i]<='9'))
	{
		flag=1;
		b[k].str[j]=y[i];
		j++;

	}


	else if(flag==1){ 
                b[k].str[j]='\0'; 
                k++; 
                j=0; 
                flag=0; 
                }

	i++;
	}

if(flag==1){ 
b[k].str[j]='\0'; 
k++; 
}

strcount2=k;

}


int LCS()
{
int i,j;

if(strcount1==0 || strcount2==0)return 0;

for(i=0;i<strcount1;i++)for(j=0;j<strcount1;j++)d[i][j]=0;

for(i=1;i<=strcount1;i++)for(j=1;j<=strcount2;j++)
{

if( !strcmp(a[i-1].str,b[j-1].str) ) d[i][j]=1+d[i-1][j-1];

else { if(d[i][j-1]>d[i-1][j])d[i][j]=d[i][j-1];
         else d[i][j]=d[i-1][j];
     }

}

return d[i-1][j-1];
}


void main()
{


	int n,casecount=0;

	while(1)
	{

	if(scanf("%[^\n]",x)==EOF)break;
	scanf("%c",&n);     // removing the newline after input
	if(scanf("%[^\n]",y)==EOF)break;
	scanf("%c",&n);     //  removing the newline after input


	casecount++;

	if( !strcmp(x,"") || !strcmp(y,"") ){ 
                printf("%2d. Blank!\n",casecount); 
                continue; 
                }

	makelist_1();
	makelist_2();

	n=LCS();

	printf("%2d. Length of longest match: %d\n",casecount,n);

	}


}

THANK YOU VERY MUCH !!!

[yiuyuho]

So digits are also intended to be considered? I though all non-letter characters should be treated as space, because the problem did not define punctuation, so I had the impression that all non-letter should not be considered.

Well, thx for the clarification.

[yiuyuho]

Also, the term "longest match" is not very clear wether it is longest common substring (continuous) or longest common subsequence (dont have to be continuous). Although now I know it should be longest common subsequence.

[Nemo]

what's wrong with this code? get WA

Code: Select all

#include <stdio.h>
#include <ctype.h>
#include <string.h>

void main()
{
//	#ifndef ONLINE_JUDGE
//	#endif	

	char xl[1002], yl[1002];

	char x[1002][20];
	char y[1002][20];
	int c[120][120] = {0};

	int i, j, count = 0;
	
	while (gets(xl) && gets(yl)) {
		count++;

		printf("%2d. ", count);
		if (strlen(xl) == 0 || strlen(yl) == 0) {
			printf("Blank!\n");
			continue;
		}

		char *ch;
		for (ch = xl; *ch; ch++)
			if (!isalnum(*ch))
				*ch = ' ';

		for (ch = yl; *ch; ch++)
			if (!isalnum(*ch))
				*ch = ' ';

		i = 1;
		char *tok;
		for (tok = strtok(xl, " "); tok; tok = strtok(NULL, " "), i++)
			strcpy(x[i], tok);

		int m = i - 1;

		j = 1;
		for (tok = strtok(yl, " "); tok; tok = strtok(NULL, " "), j++)
			strcpy(y[j], tok);

		int n = j - 1;

		for (i = 1; i <= m; i++)
			for (j = 1; j <= n; j++)
				if (strcmp(x[i], y[j]) == 0)
					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];

		printf("Length of longest match: %d\n", c[m][n]);

	}

	
}

[mf]

There can be more than 119 words in a line. You should increase the size of your c[][] array.

[Nemo]

thank you so much!
I got AC.

[jaracz]

Hi guys!!
Why I'm gettin' WA!!

What should be ouput for

Hello!
***

where * is white space

my prog print "1. Length of longest match: 0"

my code:

Code: Select all

look down 

[Sedefcho]

I think you have slightly misunderstood the problem.


INPUT

Code: Select all

This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
The document provides late-breaking information
breaking late document
The document provides late-breaking information
The provides document
The document provides late-breaking information
The provides information

OUTPUT

Code: Select all

 1. Length of longest match: 1
 2. Blank!
 3. Length of longest match: 2
 4. Length of longest match: 1
 5. Length of longest match: 2
 6. Length of longest match: 3

I think these test cases will help you.

[jaracz]

Thanks a lot, these tests helped me understand this pro correctly
have to rebuild a bit my code now:)

[jaracz]

Now my prog passed your tests, but still WA
here's my code

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define max 1001

int isblank(char *a)
{
    for(char *i = a; *i; i++)
    if(!isspace(*i))return 0;
    return 1;
}    

void clear(char *a,char *b)
{
    for(char *i = a; *i; i++)
    if(!isalnum(*i))*i = ' ';
    for(char *i = b; *i; i++)
    if(!isalnum(*i))*i = ' ';    
}    

int main()
{
    int how = 0;
    char str1[max],str2[max],word[21],word2[21];
    while(gets(str1) && gets(str2))
    {
        if(!strlen(str1)||!strlen(str2))
        {
            printf("%2d. Blank!\n",++how);
            continue;
        }    
        clear(str1,str2);
        int count = 0;char *i = str1, *j = str2;
        while(!isblank(str1) && !isblank(str2))
        {
            if(!isblank(str2))sscanf(str2,"%s",&word);
            while(isspace(*j))j++;
            while(isalnum(*j))*j++ = ' ';
            if(!isblank(str1))sscanf(str1,"%s",&word2);
            while(isspace(*i))i++;
            while(isalnum(*i))*i++ = ' ';
            while(strcmp(word,word2) && !isblank(str1))
            {
                if(!isblank(str1))sscanf(str1,"%s",&word2);
                while(isspace(*i))i++;
                while(isalnum(*i))*i++ = ' ';
            }    
            if(!strcmp(word,word2))count++;
        }    
        printf("%2d. Length of longest match: %d\n",++how,count);
        word[0] = word2[0] = '\0';
    }    
    return 0;
}       

any other suggestions?

[boshkash1986]

i tried every possible test case posted on the forum and they gve me exactly the same answer as mine
Can anyone help me


Another Question:
when the input is like this

Code: Select all

    (5 Spaces)
hello

would the output be

Code: Select all

Blank!

OR

Code: Select all

1. Length of longest match: 0

Please can anyone help me

[mamun]

I get

Code: Select all

 1. Blank!