|
||
Title: Pattern Matching Post by hary on Sep 17th, 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 17th, 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.) |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |