Computer Science 2311
Spring 2005
Laboratory Assignment 10

Handed out: 4/13/05

Read this entire assignment before beginning to work on it.

The assignment

In class we looked at a way to determine whether one string occurs as a substring of another. This assignment has you solve the same problem in a different way.

Write a Java program that reads two strings from the user and then tells the user whether the first occurs inside the second.

How to solve the problem

Earlier in the term you used recursion to solve a simple problem. For this exercise you will use recursion again.

Recall that recursion is a substitute for looping. To use recursion, you just let a function call itself. Recursion yields short and simple implementations of a wide variety of algorithms.

Write a class SubstringTester with the methods shown below. Use recursion instead of loops. Copy these headings and contracts into your program.

Objects of your class should have two variables called P and T, of type String. They are the pattern and text that your object works with.

  //============================================================
  //                         SubstringTester
  //============================================================
  // This initializes an object to hold a particular pattern
  // and text.
  //============================================================

  public SubstringTester(String P, String T)

  //============================================================
  //                         occurs
  //============================================================
  // occurs() returns true if string P occurs as a substring
  // of string T.  (P and T are the strings in this object.)
  //
  // For example, if P is "luck" and T is "Frederick is a lucky man"
  // then occurs() returns true.
  //============================================================

  public boolean occurs()

  //============================================================
  //                         occursAfter
  //============================================================
  // occursAfter(k) returns true if string P occurs  
  // as a substring of string T, starting at an index
  // that is greater than or equal to k.  (The first character
  // is at index 0.)
  //
  // For example, if P is "luck" and T is "Frederick is a lucky man"
  // then occursAfter(5) returns true, but occursAfter(19) returns
  // false.
  //============================================================

  private boolean occursAfter(int k)

  //============================================================
  //                         occursAt
  //============================================================
  // occursAt(k) returns true if string P occurs
  // as a substring of string T at index k.
  //
  // For example, if P is "luck" and T is "Frederick is a lucky man"
  // then occursAt(15) returns true, since "luck" occurs at index
  // 15 of T, but occursAt(10) returns false.  
  // (Blanks count as characters.)
  //============================================================

  private boolean occursAt(int k)

  //============================================================
  //                         suffixOccursAt
  //============================================================
  // suffixOccursAt(k,n) returns true if the length n suffix
  // of string P occurs as a substring of string T at index k.
  //
  // For example, if P is "luck" and T is "Frederick is a lucky man"
  // then suffixOccursAt(17,2) returns true, since the length
  // 2 suffix "ck" of P occurs starting at index 17 in T.
  //============================================================

  private boolean suffixOccursAt(int k, int n)

Requirements

You are required to implement these functions directly using recursion. So, for this assignment, you are not allowed to use any kind of loop. (No do, for or while, for example.)

Also, do not use powerful operations of the string class, such as indexOf and substring, for this exercise. The only string class methods that you should need are length and charAt.

Hints

The occurs method is very easy; just use occursAfter to do the job. How can you implement occurs if you have occursAfter?

The occursAt method is also very easy; just use suffixOccursAt. How can you implement occursAt as a single call to suffixOccursAt?

For occursAfter, you will need to pay attention to lengths. Watch out for a call occursAfter(k) where k is so large that there is not even enough room for the P to occur in T at index k (let alone at larger indices) because there are not enough characters left in T.

Once you have dealt with the length issue, and have concluded that there are enough characters left to look at, then you should realize that P occurs at or after index k if it either occurs at index k, or it occurs at or after index k+1.

Use similar ideas to implement suffixOccursAt. Think about how to computer suffixOccursAt before you try to code it in Java. What are special, easy, cases? What about more general cases? Does the idea work on paper?