## 475 - Wild Thing

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

### 475 - Wild Thing

i am getting WA, i used DP, but may be my DP is wrong. Can you tell whether these recurrence relations are right or not?

Code: Select all

``````input:
pattern[1....m], and str[1.....n]

match[m][n] =
true; if m == 0 && n == 0
true; if n == 0 && m== 1 && pattern[m] == '*'
match[m-1][n-1]; if pattern[m] == str[n]
match[m-1][n] | match[m][n-1]; if pattern[m] == '*'
false; otherwise

the answer is in match[m][n]``````
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your relation set is not sufficient. Try some samples...

Input:

Code: Select all

``````*
COMFILE.DAT
COST.DATA
CAT

*AL*
ALFRED
PROG1A
PROG1A.PAS

*A*PA
ALFRED
PROG1A
SEAPAMPA
PROG1A.PAS

*A*PAM
AQPAPDM
AQPAPAM

HELLO
HELLO``````
Output:

Code: Select all

``````MATCHES FOR THE PATTERN: *
COMFILE.DAT
COST.DATA
CAT

MATCHES FOR THE PATTERN: *AL*
ALFRED

MATCHES FOR THE PATTERN: *A*PA
SEAPAMPA

MATCHES FOR THE PATTERN: *A*PAM
AQPAPAM

MATCHES FOR THE PATTERN: HELLO
HELLO``````
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
sorry, my relations do not completely reflex my source code. Jan's outputs are same as mine, please anymore test cases

Code: Select all

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

char s[50], wild[50];
bool flag[50][50], memory[50][50];

bool match(int p, int q)
{
if(p == -1)
{
if(q == -1)
return true;
return false;
}
if(q == -1)
{
if(p == 0 && wild[p] == '*')
return true;
return false;
}
if(flag[p][q] == true)
return memory[p][q];
bool result;
if(wild[p] == s[q])
result = match(p-1, q-1);
else if(wild[p] != '*')
result = false;
else
result = (match(p-1, q) | match(p, q-1));
flag[p][q] = true;
return memory[p][q] = result;
}

void main()
{
bool exit = false;
int found;
while(gets(wild))
{
found = 0;
for(;;)
{
if(gets(s) == NULL)
{
exit = true;
break;
}
if(s[0] == 0)
break;
memset(flag, false, sizeof(flag));
if(match(strlen(wild)-1, strlen(s)-1))
{
++found;
if(found == 1)
printf("MATCHES FOR THE PATTERN: %s\n", wild);
puts(s);
}
}
if(exit)
break;
if(found)
putchar('\n');
}
}``````
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Getting many PE..
I don't have any clue whats causing PE. I tried trimming leading/trailing spaces, but didn't work.
Any hint or advise will help me.

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
- Don't remove any spaces;
- If there is no match for a set, don't print anything;
- There is a blank line between two PRINTED sets.
Thiago Sonego Goulart - UFMG/Brazil
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
tgoulart wrote:- Don't remove any spaces;
- If there is no match for a set, don't print anything;
- There is a blank line between two PRINTED sets.
Thanks tgoulart Got AC.
playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal
I'm also getting WA, my wildcard method seems ok and passes the tests above any special case worth considering?
I'm getting the lines with fgets and removing the trailing \n, should I bother removing spaces or is the input well formed?
be cool...
tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
playerX wrote:I'm also getting WA, my wildcard method seems ok and passes the tests above any special case worth considering?
I'm getting the lines with fgets and removing the trailing \n, should I bother removing spaces or is the input well formed?
You don't need to worry about that.

Have you tried something like this?

Code: Select all

``````abc
aabc
abcc
abcabc
abc
abbc
abc``````
Thiago Sonego Goulart - UFMG/Brazil
ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
cannot get rid of PE's. my output format for the sample inputs are
MATCHES FOR THE PATTERN: C*AT
COMFILE.DAT
CAT
COAT
//one blank line
MATCHES FOR THE PATTERN: *A*
MOUNTAIN.TXT
ALFRED
PROG1A
PROG1A.PAS
//one blank line
MATCHES FOR THE PATTERN: B**N*
BANANA
BNXJ.25
BORN
BRANDISH.SRD
BITNET
Press any key to continue_

i took input with gets, didnt remove any blanks, still PE.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program