Wednesday, March 2, 2011

WAP to WildCard Patern Matching

Write pattern matching algorithm i.e isMatch(String,Pattern)
Pattern can have ?(one character) and *(many characters). ex. abbdef and a?b*f are a match aaabab and a*ba are not a match


#include
using namespace std;
//check regexp against text recursively
bool match(char *regexp, char *text){
// the case regexp is empty, we don't need to check text == '\0'
if (*regexp == '\0') return (*text == '\0');
// the case ? and normal characters
if (*regexp == '?'||*regexp == *text) return match(regexp+1,text+1);
// the case *
if (*regexp=='*'){
do{
if (match(regexp+1,text)) return true;
}while (*text++!='\0');
}
return false;
}

int main(){
char p[4]={'a','*','d'};
char s[4] = {'a','c','b'};
bool k=match(p,s);
if(k) cout<<"yes";
else cout<<"no";
return 0;
}

No comments :