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

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

475 - Wild Thing

Post 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]
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
Location: Dhaka, Bangladesh
Contact:

Post 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.
Ami ekhono shopno dekhi...
HomePage

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

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

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

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post 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.
Thiago Sonego Goulart - UFMG/Brazil

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post 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?
be cool...

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post 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
Thiago Sonego Goulart - UFMG/Brazil

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

Post 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.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Post Reply

Return to “Volume 4 (400-499)”