## 10100 - Longest Match

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

### 10100 Longest Match

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
I think in the first case the output should be 2.

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
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?
We are all in a circular way, no advances, only moving and moving!

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

### Re: 10100 Longest Match

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:
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
/*@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*/

******

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

### help

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

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

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

sayeed
New poster
Posts: 8
Joined: Wed Aug 07, 2002 9:00 pm
hey sjn
Can you see any error in my code? Is there any difference with your code
Pls let me know

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
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,

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

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

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

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 ?

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

### 10100 - Longest Match

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]