// search_pattern.cpp
 
 
/**
  * @app       Search substring using wildcards
 * @author     vishesh yadav
 * @website    http://vishesh.exofire.net
 *
 **/
 
 
#include <iostream>
 
 
 
/**
 * @descp Search 'substr' with wild cards in 'str'
 * @param
 *    str    :  pointer to string in which substr is to be searched
 *    substr :  pointer to string to be searched, wild card allowed
 
 * @returns  true is 'sunstr' is inside 'str', else false
 *
 * @notes
 *    in case '*', '?' or '\' chars are part of 'str' use '\' in 'substr'
 *    followed by desired character, for not using them as wild cards but
 *    as a part of 'str'.
 *
 * @example
 *    "vishesh", "*is??h"
 *    "*goal??", "\*g??\?*"
 *
 **/
 
 
bool search(const char *str, const char *substr);
 
 
int main(int argc, char* argv[])
{
    using namespace std;
 
    const int MAX = 25;
    char s1[MAX], s2[MAX];
 
    cout << "Enter String         : ";
    cin.getline(s1, MAX);
 
    cout << "Enter Search Pattern : ";
    cin.getline(s2, MAX);
 
 
    if ( search(s1, s2) )
        cout << "\n\"" << s2 << "\" " << "found in \"" << s1 << "\"";
    else
        cout << "\n\"" << s2 << "\" " << "not found in \"" << s1 << "\"";
}
 
 
bool search(const char *str, const char *substr)
{
    bool x = false;
 
    if ( *substr == 0 )
        return true;
    else if ( *str == 0 )
        return false;
    else if ( *substr == '\\' )
        return search( str, ++substr );
    else if ( *substr == '*' )
    {
        // try every possible substring of 'str' until satisfied
        while ( *str )
            if ( x |= search( str++, substr+1 ) )
                return true;
        return false;
    }
    else if ( *substr == '?' )
        return search( ++str, ++substr );
    else if ( *substr == *str )
        return search( ++str, ++substr );
    else if ( *substr != *str )
        return search( ++str, substr ); // to make "she" a part of "vishesh"
    else
        return false;
    return true;
}