475 - Wild Thing

[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]

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

[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');
	}
}

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

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

[rio]

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

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?

[tgoulart]

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

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