Expert: Zlatko - 9/20/2009

Question
i have to work on two functions one to replace and another one to match strings using pointers.

char *strmatch(char *str, char *s)
so if *str was: "Hello my name is Nick."
and *s was: "my n"
strmatch would output:ame is Nick.
if nothing is matched strmatch would output null. I need to use a driver.c to read in the two lines from stdin using fgets.

I have little to no idea on how to go about starting this so any help would be appreciated.

Answer
Hello Nick.

I'm glad to help, but I have to remind you that thinking about the strmatch algorithm is a good mental exercise. Thinking about how to do it will make you a better programmer and prepare you for your exams. Ok, that's my public service announcement. Lets get down to it. You need a main function, which can get the user's input. The main function will pass the inputs to a test function, and the test function will call strmatch. The test function will make testing easier because you can call it directly from your program without having to repeatedly input your tests.

You are right to use fgets(), instead of gets(), because fgets let you specify how much text you can accept into your buffers. The only problem is that fgets saves the newline character that the user inputs, but gets discards it. We'll use a little helper function to remove the newline.

Below is the program. Read the comments and try to think about how you would implement parts of it before reading the code. If you cannot make any progress, then step through the program with a debugger. Examine the variables at each step to understand how it works.

Feel free to follow up if you have any questions.



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

/* strmatch tries to find the toFind string in the
toSearch string. If it is found, the function returns a pointer
to just past the found string in toSearch. If it is not found,
the function returns NULL.

The function starts at the beginning of toSearch, and the
beginning of toFind. It keeps track of where it started in
pStart.

It uses pSearch and pFind to access characters in toSearch and
toFind. It checks the two strings character by character.
On a mismatch, the pFind is rewound to the start of toFind and
the pSearch is sent back to one past the start of the previous
search. So, on a mismatch, pSearch gets pStart + 1 and the
matching starts all over again.

Whenever there is a match, both pSeach and pFind get advanced.
If the function gets to the end of pFind, it means a match has been
found. The pSearch points to just past the match and so it is returned.
*/
char* strmatch(char* toSearch, char* toFind)
{
   char* pSearch = toSearch;
   char* pStart = toSearch;
   char* pFind = toFind;

   while(*pSearch != 0)
   {
       if (*pSearch == *pFind)
       {
           /* characters match */
           ++pFind;
           ++pSearch;
           if (*pFind == 0)
           {
               return pSearch;
           }
       }
       else
       {
           /* characters mismatch, rewind the pFind to the start of toFind */
           pFind = toFind;
           pSearch = pStart + 1;
           pStart = pSearch;
       }
   }
   return NULL;
}

/* chomp - is named after the chomp function in the Perl language
and it does the same thing. If a string ends in a newline character,
the newline character is erased from the string.
*/
void chomp(char* s)
{
   char* pLastChar;

   /* check s for NULL. This is a little bit of defensive programming */
   if (s == NULL) return;

   /* find the pointer to the last character in the string */
   pLastChar = s + strlen(s) - 1;

   /* if the last character is a newline, set the last character to 0
   thus ending the string at the location of the newline. */
   if (*pLastChar == '\n') *pLastChar = 0;
}

/*
test is a test setup for the strmatch function
*/
void test(char* toSearch, char* toFind)
{
   char* found = strmatch(toSearch, toFind);
   printf("-----------------------------------------------\n");
   if (found != NULL)
   {
       printf("'%s' was found in '%s'\n", toFind, toSearch);
       printf("After it comes '%s'\n", found);
   }
   else
   {
       printf("'%s' was NOT found in '%s'\n", toFind, toSearch);
   }

}

/* set BATCH_TEST to 1 to run automatic test cases
set it to anything else to run interactively.
*/
#define BATCH_TEST 1

int main(void)
{
#if BATCH_TEST == 1

   test("aaaabcd", "aab");
   test("abcd", "ab");
   test("abcd", "cd");
   test("abcd", "xy");
   test("Hello my name is Nick.", "my n");

#else

   char stringToSearch[128];
   char stringToFind[128];
   char* found = NULL;

   while(1)
   {
       printf("Enter the string to search\n");
       fgets(stringToSearch, sizeof(stringToSearch), stdin);
       chomp(stringToSearch);
       printf("Enter the string to find\n");
       fgets(stringToFind, sizeof(stringToFind), stdin);
       chomp(stringToFind);

       test(stringToSearch, stringToFind);
   }
#endif
   return 0;
}