Challenge - String Search Challenge Solution

String Search Challenge Solution

#include <iostream>

using namespace std;

int count_asterisks(char *str)
{
	int asterisk_count = 0;
	for(int x=0; x<strlen(str); x++)
	{
                if(str[x] == '*' && (x == 0 || str[x-1] != '\\'))

		{
			asterisk_count++;
		}
	}
	return asterisk_count;
}
bool match_within(char *, char *);

bool match_at_front(char * search_in, char * search_for)
{
	if(search_for[0] == '\0') //everything matches
	{
		return true;
	}
	else if(search_in[0] == '\0') //end of first string
	{
		return false;
	}
	else if(search_for[0] == '*')
	{  //any number of initial characters are chewed up by the *
	    return match_within(search_in, (search_for+1));
	}
	else if(search_for[0] == '\\' && search_for[1] == '*')
	{
		if(search_in[0] == '*')
		{
			return match_at_front(search_in + 1, search_for + 2);
		}
		else 
		{
			return false;
		}
	}
	else if(search_for[0] == search_in[0])
	{
		return match_at_front(search_in+1, search_for+1);
	}
	else
	{
		return false;
	}
}
	
bool match_within(char * search_in, char * search_for)
{
	for(int x=0; 
	    x<=strlen(search_in)-strlen(search_for)-count_asterisks(search_for); x++)
	{
		if(match_at_front(search_in+x, search_for))
		{
			return true;
		}
	}
	return false;
}					
int main(int argc, char* argv[])
{
	if(argc != 3)
	{
		cout<<"Input should be of the form substring str1 str2";
		return 0;
	}
        if(match_within(argv[1], argv[2]))
        {
                cout<<"String "<<argv[2];
                cout<<" is contained within "<<argv[1]<<".";
        }
        else
        {
                cout<<"String "<<argv[2]<<" is not contained within ";
                cout<<argv[1]<<".";
        }
}

Download Source

The logic behind this solution is that search_within searches to find if at any place in the first string, the second string matches the next part of the first string. The find_at_front function is used to check if at any given starting spot in the first string, the second string matches. The trick to handle is asterisk matching any number of characters is that an asterisk matches any number of characters, so when an asterisk appears at the beginning of a string, that means that whatever remains of the string after the asterisk should match as a substring of the first string. And because of the way find_at_front recursively moves down each string, whenever an asterisk occurs in the second_string, it will be at the front, so we test to see if the remainder of the second string is a substring of the first string.

Notice the use of pointer arithmetic to simplify the manipulation of the strings.

Many other solutions exist! If yours doesn't match the Cprogramming.com key, but it still works, let us know and we'll upload it as an alternative answer.