Page 1 of 1

475 - Wild Thing

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

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

*AD*M*AD*M
ADPAPDMAM
ADPAPAMADFM
ADAPMAABSD

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: *AD*M*AD*M
ADPAPAMADFM

MATCHES FOR THE PATTERN: HELLO
HELLO
Hope it helps.

Posted: Tue Jun 06, 2006 8:00 am
by ayon
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
by rio
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.

Thanks in advance.

Posted: Sat Mar 24, 2007 7:10 pm
by tgoulart
- 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
by rio
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 :D Got AC.

Posted: Sun Apr 08, 2007 8:51 pm
by playerX
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
by tgoulart
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
by ayon
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.