Thread: Searching

In my book there is a exercise for me to try and do a search which is both case sensitive and insensitive

I did it however Im interested in knowing if there is an easier way or more efficient way

Code:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

char *caseSensitive(char *string, char *match);
char *caseInSensitive(char *string, char *match);

int main(void)
{
	
	char string[100], match[100], *ptr, *pos;
	int searchtype;
	
	printf("Enter a string to be searched: ");
	fgets(string, sizeof string, stdin);
	
	if ((ptr=strchr(string,'\n'))!=NULL)
		*ptr = '\0';
	
	printf("String to match: ");
	fgets(match, sizeof match, stdin);
	
	if ((ptr=strchr(match,'\n'))!=NULL)
		*ptr = '\0';
	
	printf("\n1 for case sensitive search\n2 for case insensitive search\n");
	scanf("%d",&searchtype);
	
	if (searchtype == 1)
	{
		pos = caseSensitive(string, match);
		if (pos==NULL)
			printf("%s wasnt found in %s\n",match,string);
		else
			printf("%s was found in %s at position %d\n",match, string,(pos-string));
	} 
	else
	{
		pos = caseInSensitive(string, match);
		if (pos==NULL)
			printf("%s wasnt found in %s\n",match,string);
		else
			printf("%s was found in %s at position %d\n",match, string,(pos-string));
	}
	
	return 0;

}

char *caseSensitive(char *string, char *match)
{

	char *pos;
	pos = strstr(string,match);
	return pos;

}

char *caseInSensitive(char *string, char *match)
{
	
	char *pos;
	int i;
	
	for (i=0;i<strlen(string);i++)
		(string)[i]=tolower((string)[i]);
	
	for (i=0;i<strlen(match);i++)
		(match)[i]=tolower((match)[i]);
	
	pos = strstr(string,match);
	return pos;

}

Code:

	for (i=0;i<strlen(string);i++)
		(string)[i]=tolower((string)[i]);
	
	for (i=0;i<strlen(match);i++)
		(match)[i]=tolower((match)[i]);

What if either string or match is a string literal? C does not allow you to change the characters of a string literal, so your function would fail. You might make a copy of each string, but that is not efficient. It is better in this case not to use the standard string library.

Originally Posted by Sebastiani

>> pos = strstr(string,match);

isn't the point of this excercise to write your *own* version of strstr?

>> (string)[i]=tolower((string)[i]);

big no no. the function should not modify the contents of the arguments in this case.

No its wasnt the point it was to use it in away that would allow case sensitve and case insensitive searches which where required to be one function each.

(string)[i]=tolower((string)[i]);

So if i used a pointer within that function to point to string and use that new pointer e.g.

Code:

char *caseInSensitive(char *string, char *match)
{
	
	char *pos, *string2, *match2;
	int i;
	
	for (i=0;i<strlen(string);i++)
		(string2)[i]=tolower((string)[i]);
	
	for (i=0;i<strlen(match);i++)
		(match2)[i]=tolower((match)[i]);
	
	pos = strstr(string2,match2);
	return pos;

}

Would that be better as its not modifying to pointers being sent to the function.

Ren, so what would I do then in the above code I guess you say I copy it what is a more efficient way.

Code:

char *caseInSensitive(char *string, char *match)
{
	
	char *pos, *string2, *match2;
	int i;
	
	for (i=0;i<strlen(string);i++)
		(string2)[i]=tolower((string)[i]);
	
	for (i=0;i<strlen(match);i++)
		(match2)[i]=tolower((match)[i]);
	
	pos = strstr(string2,match2);
	return pos;

}

This will fail too. string2 and match2 do not point to memory you can write to. The right way to copy is this.

Code:

char *caseInSensitive(char *string, char *match)
{
	
	char *pos;
        char *string2 = malloc(strlen(string) + 1);
        char *match2 = malloc(strlen(match) + 1);
	int i;
	
	for (i=0;i<strlen(string);i++)
		(string2)[i]=tolower((string)[i]);
	string2[i] = '\0';
	for (i=0;i<strlen(match);i++)
		(match2)[i]=tolower((match)[i]);
	match2[i] = '\0';
	pos = strstr(string2,match2);
        free(match2);
	return pos;

}

Problem now is pos does not point within string, so you can not free string2 and changes to pos will not be reflected in string. A better and more efficient way is to rewrite strstr using toupper or tolower when comparing characters.

Originally Posted by itsme86

Except that then you're doing toupper/tolower on each character N times where N is the number of characters in the match substring. I'm not sure that's more efficient especially for large substrings.

Not more efficient than what? Calling malloc twice to make copies? Or modifying the original string to be upper or lower case?

Performance is at most 2N * M times where M is the number of unsuccessful matches and N is number of characters in the match substring because toupper or tolower is used on both source and search string. Performance is N + M where N is the length of source string and M is the length of search string for modifying both source and search string, and two malloc and free calls are almost sure to be much slower. Not to mention memory use for a copy of source and search string and harder code to fix the problem of returning a pointer within the original search string.

Copying is not a good solution because it is slow and is not as simple to do right. Modifying the original string is really not a good solution because it fails for a string literal or permanently changes both strings. The fastest, simplest and shortest correct code using the least memory is strstr rewritten with toupper or tolower for comparisons.

strdup() (SVID3 compliance) is a reasonable way to clone strings for testing.
Assuming the OP is on unix. I don't know if VC++ or .net has strdup().

Originally Posted by [Ren]

Not more efficient than what? Calling malloc twice to make copies? Or modifying the original string to be upper or lower case?

Performance is at most 2N * M times where M is the number of unsuccessful matches and N is number of characters in the match substring because toupper or tolower is used on both source and search string. Performance is N + M where N is the length of source string and M is the length of search string for modifying both source and search string, and two malloc and free calls are almost sure to be much slower. Not to mention memory use for a copy of source and search string and harder code to fix the problem of returning a pointer within the original search string.

Copying is not a good solution because it is slow and is not as simple to do right. Modifying the original string is really not a good solution because it fails for a string literal or permanently changes both strings. The fastest, simplest and shortest correct code using the least memory is strstr rewritten with toupper or tolower for comparisons.

Not sure Im ready to modify built in functions just yet still relatively new to C and not 100% sure on how strstr checks the strings

I thought it would be simple however didnt think it to be that simple. So follow how strstr does it to point to the first occurance if find-me is found or NULL or 0 if not. However to make it case-insensitive wouldnt I still need to copy the match and string variables.