CPSC 333: Source Code for ``Buggy Matching Program''

Location: [CPSC 333] [Assignments] [Assignment 5] Source Code

This page was most recently modified on April 3, 1997

Note: While you can view this file using a web browser, you shouldn't use it in order to work on Assignment 5; please use the source code that's included in the directory

~eberly/CPSC333/A5

instead. The version listed below has been edited in order to ensure that various special characters (``<'', ``>'' ``&'') display properly, so you definitely won't be able to copy the source code given in this file, below, and hope that it can be compiled. On the other hand, the source code located in the above directory has not been edited in any way, and can be compiled using CC.

//***************************************************************
//
// This program prompts for and accepts a short source string
// (with length at most 50) and a short pattern string (with
// length at most 20) and then finds the beginning of the last
// occurrence of the pattern in the source.
//
// It then returns the offset (position) of this occurrence if one
// is found, and reports that the pattern was not found otherwise.
//
// For example, If the source string is "The time has come" and the
// pattern is "The" then the program should report that the pattern
// is last found beginning at position 0; if the source is the
// same, and the pattern is "has" then the program should report
// that the last occurrence of the pattern begins at position 9.
// If the pattern is the empty string then the "position" reported
// will be the length of the source string.
//
// If the user's source or pattern (or both) are too long then the
// user is informed of this problem and the program uses a prefix
// of the input, of the maximum allowed input.
//
//****************************************************************

#include <iostream.h>
#include <string.h>

short int myGetString(char*, int);
short int isPrefix(char*, char*, int);

int main()      // Type defined for use with older compilers
{
  const int max_source_length = 50;
  const int max_pattern_length = 20;

  char source[max_source_length + 1] = "\0";
  char pattern[max_pattern_length + 1] = "\0";

  int source_length, pattern_length, offset;
  short int found;

  //
  // Prompt for and obtain the inputs. Use a prefix of an input
  // string, and report this, if either input is too long.
  //

  cout << "Please enter source string: ";
  if (myGetString(source, max_source_length) > 0)
    cout << "Source string is too long; a prefix will be used." << endl;
  source_length = strlen(source);

  cout << "Please enter pattern: ";
  if (myGetString(pattern, max_pattern_length) < 0)
    cout << "Pattern is too long; a prefix will be used." << endl;
  pattern_length = strlen(pattern);

  //
  // Check for occurrences of the pattern in the string, using all
  // possible offsets in decreasing order.
  //

  found = 0;
  offset = source_length - pattern_length - 1;

  while ((offset >= 0) && (found == 0))
  {
    if (isPrefix(source, pattern, offset) == 1)
      found = 1;
    else
      offset = offset - 1;
  } //end while

  if (found == 1)
  {
    cout << "Last occurrence of the pattern begins at position ";
    cout << offset << endl;
  }
  else
    cout << "The pattern was not found." << endl;

} //end main()

//*****************************************************************
//
// Function myGetString accepts a string and a length bound as
// inputs, and tries to set the value of the string using input
// supplied on a single line. If the user's input is too long
// (that is, it exceeds the given length bound) then a prefix of
// maximum possible length is used to define the string.
//
//*****************************************************************

short int myGetString(char *outString, int maxLength)
{
  int i;
  char c;

  i = 0;
  while (i < maxLength)
  {
    cin.get(c);
    if (c == '\n')
    {
      outString[i] = '\0';
      return(0);
    }
    else
    {
      outString[i] = c;
      i = i + 1;
    }; //end if
  }; //end while

  outString[maxLength - 1] = '\0';

  //
  // Input was either of maximal length, or too long; check which,
  // read rest of input line, and return the appropriate status
  // value as output

  cin.get(c);
  if (c == '\n')
    return(0);
  else
  {
    while (c != '\n')
      cin.get(c);
    return(1);
  }; //end if
} //end myGetString

//******************************************************************
//
// Function isPrefix accepts a pattern, source, and an integer
// offset as inputs, and checks whether the source string includes
// a copy of the pattern that begins at the given offset position.
//
// Value returned is 0 if a copy of the prefix was not found in this
// position and is 1 otherwise.
//
// Assumptions:
//
//  (1) offset >= 0
//  (2) offset + strlen(pattern) <= strlen(source)
//
//******************************************************************

short int isPrefix(char *pattern, char *source, int offset)
{
  int pattern_length, i;

  pattern_length = strlen(pattern);

  i = 0;
  while (i < pattern_length)
  {
    if (pattern[i] == source[offset + i])
      i = i + 1;
    else
      return(0);
  }; //end while

  return(1);
} //end isPrefix

Location: [CPSC 333] [Assignments] [Assignment 5] Source Code