CS 112 A1 - Fall 2004: Homework 3

Due Tuesday, October 26, 11:59 P.M.

Reading: Chapters 6, pages 233-242 and chapter 7, pages 268 - 315.

Please keep in mind the policy on collaboration.

PROBLEM (50 points):

Submit one file called find.cpp. In this file write a function

int find(string s, string t)

that employs a recursive algorithm to test whether the string t is contained in the string s. If so, it outputs the offset of every match of t in s and returns 1. If not, it outputs "no occurrence" and returns 0. For example,

find("Mississippi", "is") outputs 1, 4 and returns 1.

find("Mississippi", "Miss") outputs 0 and returns 1.

find("Mississippi", "pi") outputs 9 and returns 1.

find("Mississippi", "hip") outputs "no occurrence", and returns 0.

Hint: First write the function which finds the first occurrence of t in s, then worry about the loop which find all of the occurrences. For the "find" function, if t is longer than s, you can return -1. Otherwise, compare t and the initial substring of s with t.length() characters. If those are the same strings, then output 0. Otherwise call the function recursively with the tail of s (that is, s without the first character).

Note: Only submit the function int find(string s, string t) in find.cpp. Do not submit a program main(). You cannot add input arguments, change types, or otherwise make changes to the function interface as defined in the prototype: int find(string s, string t);.

Documentation required for hw3:

For problem 3 you should make sure that your program file is well-commented, formatted and observes the usual rules of good programming.

You should also submit a users manual for the find program in a file called find.txt.

To submit hw3:

  1. You must be logged onto csa, and all files must be on the csa computer.
  2. Test that your program works by compiling it with g++ -Wall.
  3. Create a subdirectory called hw3, using the mkdir command.
  4. Copy all files to be submitted and no others into this subdirectory. The following files (and ONLY these files) should be in subdirectory hw3:
  5. To submit the assignment, cd to the directory containing the hw3 subdirectory and type:
    gsubmit cs112 -cp hw3
    This should submit the entire hw3 subdirectory.