Author |
Topic: Pattern Matching (Read 3203 times) |
|
hary
Junior Member
Posts: 107
|
 |
Pattern Matching
« on: Sep 17th, 2013, 2:55pm » |
 Quote  Modify
|
Given an input string and a pattern (pattern could consist of wildcard character *, all other wild card characters be treated as normal characters except *).
How can we tell that the pattern is actually a string pattern
(NOTE: there could be more than one occurrence of * in the pattern as well)
e.g. The first string is input text and second string is pattern in the below examples
"This is the text", "This is*xt" -> true
"This is the text", "This is*rxt" -> false
"This is the text", "*" -> true
"This is the text", "*is" -> false
"This is", "This is" -> true
"This is my string", "is" -> false
"This is" "This *"->true
"This is" "*" -> true
I know we have regex constructs to do this in some of the programming languages. What I am trying to figure out is a simple C/C++ code/algo to achieve the same.
|
| « Last Edit: Sep 17th, 2013, 3:05pm by hary » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Pattern Matching
« Reply #1 on: Sep 17th, 2013, 10:43pm » |
Quote Modify
|
You can turn it into a substring matching problem. Just split the pattern at *, then search for each part in the string (such that they are all found one after the other; and you can do this greedily).
So e.g. "This is*xt" is split into "This is" and "xt" ; we can find "This is" at the start of "This is the text", and then we need to find "xt" in the remainder (" the text") which matches near the end. All parts are found in sequence, so the pattern matches the string.
Another option is to build a finite state machine corresponding to the pattern to parse valid strings. (Which is what happens with regex implementations behind the scene.)
|
| « Last Edit: Sep 17th, 2013, 10:44pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print