Hi Harshal,
The question is a bit unclear, especially given the *win and *def* pattern.
Does it mean anything before "win" is acceptable or anything before and
after "def" is acceptable? or is it like 'a' repeated any number of times
followed by 'b' repeated any number of times... in a*b*cd*?
I am assuming the pattern match has to looking for any character wherever
'*' is given. Thats the first one I mentioned above.
The solution to the second kind will be a little more involved.
This is how I would think of implementing it:
we should have a list of wildcards we support, suppose for now we support
only '*'
1. The search string can be called our query.
2. the query can be splitted into substrings whereever a wild card appears.
special cases include it appears in beginning and end.
3. we need to find the splitted strings, if they appear in the same order in
the as they appear in the query
for doing this we could have an array of the substrings and the indexes
at which they appear in the text,
if the indexes of appearances are in ascending order we know the
substrings exist.
the index of appearance of first and last substring might be needed in
the final response if we need to tell where exactly the string appears. For
now this will be able to handle only one occurrence of the pattern and can
be reformed to include more than one occurrences.
4. our next step includes matching to see if they fit as per our wild cards.
for * in beginning the of query the start index of the response could be the
beginning of the text similarly for end it could be the end of text given
step 3 returned a positive response, i.e substrings exist in order. if other
wildcards are involved we can think of checking the behaviour differently.
If we assume '*' means repetition of the previous char given:
1. we will have to start the parse the text along with the query.
2. looking for the first char (having a * in beginning doesnt make sense in
this case) in the query in the text. if there is a wild card, we look for
the wild card behavior in the text, repetition, etc.wherever the behavior
seems to end we look ahead in the query to see which is the character after
the wild card in the query if it matches with the character in text we move
further on the query and text or reset the query parse pointer to point to
beginning of query string. if the second character is not a wild card, we
just do a match and move forward if we find it in text or reset query
parsing pointer.
3. in the end if the query matches the text at any place we can fill the
response start and end pointers. for multiple occurrences if we havent
reached end of file we can reset query pointer and start finding the
complete match again.
** cases like a*ab*c may not be handled by this.
-V
On Sat, Oct 16, 2010 at 6:21 PM, Harshal <hc4...@gmail.com> wrote:
> Given a text file, implement a solution to find out if a pattern
> similar to wild cards can be detected.
> for example find if a*b*cd*, or *win or *def* exists in the text.
>
> how to take care of wild cards?
>
> --
> Harshal Choudhary
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
