## 10100 - Longest Match

Moderator: Board moderators

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

### It should be...

INPUT:
what the hell
is going on

OUTPUT:
1. Length of longest match: 0

Daniel "Naz
Daniel
UFRN HDD-1
Brasil

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

### Output

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.
Daniel
UFRN HDD-1
Brasil

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 10100 Longest Match Wrong answer???????

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 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
{
printf("Length of longest match: %d\n",lcs_len(dp,dp,a,b,n1,n2));
}
total++;
}
}

{
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];
}
Mr. Arithmetic logic Unit

Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

### 10100 WA, confused, Plz Help !!

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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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
New poster
Posts: 16
Joined: Thu Apr 14, 2005 10:40 am

### 10100 - Longest match -WA

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
There can be more than 119 words in a line. You should increase the size of your c[][] array.

Nemo
New poster
Posts: 16
Joined: Thu Apr 14, 2005 10:40 am

### yes!

thank you so much!
I got AC.

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

### 10100 WA

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 ``
Last edited by jaracz on Tue Jul 12, 2005 8:00 pm, edited 1 time in total.
keep it real!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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``````

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
Thanks a lot, these tests helped me understand this pro correctly
have to rebuild a bit my code now:)
keep it real!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
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?
keep it real!

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

### 10100 - Longest Match

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

`` 1. Blank!``