10100 - Longest Match

All about problems in Volume 101. 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
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

10100 Longest Match

Post by wyvmak » Sat May 04, 2002 7:54 am

would anyone tell me is this correct?

input:
The document provides late-breaking information
The breaking.
.,
,.
The34 4 document provides late-breaking information
The34 4

output:
1. Length of longest match: 1
2. Length of longest match: 0
3. Length of longest match: 2

abiczo
New poster
Posts: 7
Joined: Sat Apr 06, 2002 2:00 am
Location: Hungary

Post by abiczo » Sat May 04, 2002 7:29 pm

I think in the first case the output should be 2.

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Sun Jun 23, 2002 8:49 pm

I can't say anything special but from my point of view (according to the problem statements) the output should be :

1. Length of longest match: 1
2. Blank!
3. Length of longest match: 2

but the answer of the case 3 may be also:
3. Length of longest match: 1 :-?

What do you think? :roll:
ImageWe are all in a circular way, no advances, only moving and moving!

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Re: 10100 Longest Match

Post by Moni » Sun Jun 23, 2002 8:56 pm

wyvmak wrote:would anyone tell me is this correct?

input:
The document provides late-breaking information
The breaking.
.,
,.
The34 4 document provides late-breaking information
The34 4

output:
1. Length of longest match: 1
2. Length of longest match: 0 { I wonder why you haven't use Blank! }
3. Length of longest match: 2

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Sun Jun 23, 2002 9:09 pm

Hi, I think your interception is a bit incorect.

In the problem description it states that
In case of at least one blank line for each input output 'Blank!'.
Blank lines means there's nothing in the line, i.e. length of string = 0 (strlen(line) = 0 if you use C or C++). When there's space in the line, it's not a blank line, let alone some non-alphanumeric characters~
Therefore in the second case in the above example, there should be no appearance of 'Blank!'.

Also, it states that
Consider the non-letter punctuation characters as white-spaces.
Do you intercept that the word *non-letter* means not in the set {A,B,C,......,Z,a,b,c,.......,z}? (Correct me if I am wrong) This was also what I intercepted in the past. However when I intercepted the word *non-letter* as *non-alphanumeric*, everything is good~

Hope it helps~

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm

Post by sayeed » Wed Aug 07, 2002 9:15 pm

/*@BEGIN_OF_SOURCE_CODE*/
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int C[3][65];

int LCS(char Model[][23],char Sample[][23],int n,int m)
{

int i,j;
for(i=0;i<2;i++)
C[0] = 0;

for(j=0;j<=m;j++)
C[0][j] = 0;

for(i=1;i<=n;i++){

for(j=1;j<=m;j++){

if(strcmp(Model,Sample[j])==0)

C[i%2][j] = C[(i-1)%2][j-1]+1;


else if(C[(i-1)%2][j]>=C[i%2][j-1])
C[i%2][j] = C[(i-1)%2][j];


else C[i%2][j] = C[i%2][j-1];


}
}

return C[(i-1)%2][m];
}



int main()

{
char S1[1005],S2[1005],s1[65][23],s2[65][23];
int i,j,k,res,count = 0,n,m;

while(gets(S1)!=NULL){
gets(S2);
res = 0;
if(strlen(S1)==0 || strlen(S2)==0) res = -1;
k = 1;
for(i = 0;S1;){
j = 0;
while(isalpha(S1))
s1[k][j++] = S1[i++];
s1[k][j] ='\0';

while(!isalpha(S1)&&S1) i++;
k++;
}
n = k-1;
k = 1;
for(i = 0;S2;){
j = 0;
while(isalpha(S2))
s2[k][j++] = S2[i++];
s2[k][j] ='\0';
while(!isalpha(S2)&&S2) i++;
k++;
}

m = k-1;
count++;
if(res!=-1){
res = LCS(s1,s2,n,m);
printf("%2d. Length of longest match: %d\n",count,res);
}
else
printf("%2d. Blank!\n",count);
}
return 0;
}
/*@END_OF_SOURCE_CODE*/



******
what's the problem with the code?? Please help.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

help

Post by sjn » Thu Aug 08, 2002 2:29 pm

pls tell me what's the outputs for these inputs

aaa a a a a
a
a!aa!aaa!
aa

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm

re: SJN

Post by sayeed » Fri Aug 09, 2002 5:41 am

1. Length of longest match : 1
2. Length of longest match : 1

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Thank u

Post by sjn » Fri Aug 09, 2002 9:33 am

At last i got AC :wink:
i didn't understand the meaning of the problem at first~

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm

Post by sayeed » Fri Aug 09, 2002 10:09 pm

hey sjn
Can you see any error in my code? Is there any difference with your code
Pls let me know

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Thu Aug 15, 2002 7:57 pm

For sayeed,
It is very difficult to understand your code :-?
Always make clear codes. :) But I think you haven't understood the problem specification.

And for sjn,
Your answer will be:

1. Length of longest match: 1
2. Length of longest match: 1

Ok! :wink:
ImageWe are all in a circular way, no advances, only moving and moving!

scx
New poster
Posts: 4
Joined: Sat Sep 07, 2002 5:13 pm

10100

Post by scx » Thu Oct 17, 2002 2:51 pm

HI!
I'm confused.
First of all ... what will be the OUTPUT for:
The 34 ble ble
34 ble

??
will it be: length of longest match: 1, 2 or 3 ?
do i treat numbers just like words ?

and what is the result of:
ble ble
ble
is it 1 or 2 ?
The word ble can be found twice in the first line as you can see

PS forgive me my poor english ... I'm not native

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Thu Oct 17, 2002 3:47 pm

The answer two your two cases are 2 and 1. Treat numbers just like word. Ignore all chars which are not digits or letters.

scx
New poster
Posts: 4
Joined: Sat Sep 07, 2002 5:13 pm

ok but how about ...

Post by scx » Thu Oct 17, 2002 4:08 pm

ok but how about not empty lines
strlen(line1 != 0) and strlen(line2 != 0)
without any match

in example:

what the hell
is going on

should it be Blank! or 0 ?

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

10100 - Longest Match

Post by Maxim » Fri Apr 18, 2003 2:23 pm

Any idea how to handle the input? And, when to print "Blank!"? I print "Blank!" when there is a line with length of 0. Is that ok? This is how I read the input:

[c]int GetData(char c[MAXN][24], int* L) {

char line[1024];
char* tok;

*L = 0;
if(feof(stdin)) return 1;
gets(line);
if(!strlen(line)) return 0;
for(tok = strtok(line, empty); tok; tok = strtok(NULL, empty))
strcpy(c[(*L)++], tok);
return 1;
}

int main() {

int k;

for(k = 1; !feof(stdin); ++k) {
if(!GetData(a, &m) || !GetData(b, &n)) {
printf("%2d. Blank!\n", k); continue;
}
if(feof(stdin)) break;
Solve();
printf("%2d. Length of longest match: %d\n", k, ...);
}

return 0;
}
[/c]

Post Reply

Return to “Volume 101 (10100-10199)”