Page 1 of 1

### 475 - Wild Thing

Posted: Tue May 30, 2006 9:38 am
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

Posted: Tue Jun 06, 2006 1:35 am
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.

Posted: Tue Jun 06, 2006 8:00 am
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');
}
}``````

Posted: Fri Mar 23, 2007 10:17 am
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.

Posted: Sat Mar 24, 2007 7:10 pm
- 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.

Posted: Sun Mar 25, 2007 7:17 am
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.

Posted: Sun Apr 08, 2007 8:51 pm
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?

Posted: Sun Apr 08, 2007 9:24 pm
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``````

Posted: Thu Jul 26, 2007 5:35 pm
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.