wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Pattern Matching
        
(Message started by: hary on Sep 17^th, 2013, 2:55pm)

Title: Pattern Matching
Post by hary on Sep 17^th, 2013, 2:55pm

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.

Title: Re: Pattern Matching
Post by towr on Sep 17^th, 2013, 10:43pm

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