Mert Toka Mert Toka - 2 months ago 15
C++ Question

Simple wildcard search algorithm in C++

I have an assignment in which I have to create a search pattern including wildcard character '?'. We haven't covered anything further than loops and properties of string libraries yet, so my teacher doesn't want me to use arrays or anything we haven't covered.

My problem is to create an algorithm for the special character '?'. Do you have any idea how can I integrate it into my program without using more advanced tricks? Everything I tried is either completely wrong or has some mistakes in it.

Program should request an input from the user for the source string and then, ask for another input for search string which can include '?' in it. For example:

Source string: glorious
Search string: ?r?o

The matched string was found at index: 2
The matched string is: orio

Answer

Here is the function I came up with. Finally I found a way using limited knowledge of mine. It works, but probably performance is really bad.

Thanks for your all help, they inspired me even though I can't directly use them because of advanced-for me- techniques.

void wildcard(string source, string search)
{
    unsigned int j = 0, i = 0, z = 0;
    string s1 = "", search2 = search;
    //Starting with a null string and adding found parts to it

    /*************************IF IT STARTS WITH QUESTION MARK*************************/

    if(search.find('?') == 0)
    {
        for(; search.at(z) == '?'; z++)
            //loop make search string start without question marks.
        {
            search2 = search.substr(z + 1, search.length());
        }

        for(; j <= source.length()-search2.length(); ++j)
            //application of Brute Force Search Algoritm for this case.
        {
            while(i < search2.length() && (source.at(z+i+j) == search2.at(i) || search2.at(i) == '?'))
            {
                s1 = s1 + source.at(z+j+i);
                i++;
            }
        }

        if(s1.length() == search2.length())
            //showing results for this case.
        {
            cout << "The matched string was found at index: " << source.find(s1) - z << endl;
            cout << "The matched string is: " << source.substr((source.find(s1)-z), search.length()) << endl << endl;
        }
        else
        {
            cout << "The search string could not found in the source string." << endl << endl;
        }
    }

    /********************IF IT DOES NOT START WITH QUESTION MARK**********************/

    else
        //If it doesnot start with ?, use normal test.
    {
        for(; j <= source.length()-search.length(); ++j)
            //application of Brute Force Search Algoritm for this case.
        {
            while(i < search.length() && (source.at(i+j) == search.at(i) || search.at(i) == '?'))
            {
                s1 = s1 + source.at(j+i);
                i++;
            }
        }

        if(s1.length() == search.length())
            //results
        {
            cout << "The matched string was found at index: " << source.find(s1) << endl;
            cout << "The matched string is: " << s1 << endl << endl;
        }
        else
        {
            cout << "The search string could not found in the source string." << endl << endl;
        }
    }
}
Comments