Homework 22

1. Assume the following Declarations:

      int a = 10, b = 4, c = 2;
     char one = 'a';
     double d = 7.5, e = 2;
     string team = "Patriots”, h = "yes";

 Fill in the following table, giving the type and value of each expression.

Expression

Type

Value

team[2]

Char

t

one + 2

Int (see note)

99

h != “yes” || team == “Broncos”

Bool

False (0)

e = a / b

Double

2

‘z’ – one

Int

25

a / c == 5

Bool

true

 

NOTE:  If you add or subtract with a character, you get an integer (not a char).  If you then take that result and assign it to a variable of type char, however, then the value will be treated as a char.

 

Write a program that reads a target string A and a test string S and tells the user whether A is a substring of S.  A is a substring of S means that A appears (in order and together!) somewhere in S. For example: low is a substring of allowable (see it? "allowable"), but not of withhold (the letters are there, but not in order in "withhold"), nor in landowner (the letters are there and in order but not together in "landowner").

 

A typical run of your program should look like this:

Enter target string: act

Enter test string  : reactionary

The target act is a substring of the test string reactionary!

Turn in

  1. A handrawn picture of the string “act” and the string “reactionary” represented as arrays of characters, complete with array indices.
  2. A printout of your program, along with a screen capture showing it run on the above example.

Remember to make sure you never try to index a character outside of the string!

 

SOLUTION

1.

a

c

t

0

1

2

 

r

e

a

c

t

i

o

n

a

r

y

0

1

2

3

4

5

6

7

8

9

10

 

2. Program source code

 
#include <iostream>
#include <string>
using namespace std;
 
//prototype
bool isSubstring(string,string);
 
int main(){
    string target,test;
 
    cout << "Enter target string: ";
    cin >> target;
    cout << "Enter test string: ";
    cin >> test;
    
    if (isSubstring(target,test)){
        cout << "The target string " << target 
                        << " IS a substring of the test string " 
             << test << '.' << endl;
    }
    else{
        cout << "The target string " << target 
                        << " IS NOT a substring of the test string " 
             << test << '.' << endl;
    }
 
    return 0;
}
 

 

// Return true if 'target' is a substring (contained within) 'test'

bool isSubstring(string target, string test)

{

    for (int i=0; i < test.length(); i++)

    {

        // Is target a substring of test, starting at index i?

        // Loop (j) over all chars of 'target' to find out

        bool match = true;  // assume good to start

        for (int j = 0; j < target.length(); j++)

        {

            // If [j+i] is not a valid index, then no chance for a match

            // We need to test for this so that test[j+i] doesn't access invalid index

            // This would also be a good place to use 'break'

            if ( (j+i) > test.length() )

            {

                match = false;

            }

            else if (target[j] != test[j+i])

            {

                // The characters don't match where they need to be, so fail for

                // starting position 'i'

                match = false;

            }

        }

       

        // If we reach here and match is still true, we found a

   // real match (starting at position i)

        if (match)

        {

            return true;

        }

    }

 

    // If reach here, never found a match

    return false;

}

 

 

 

syntax highlighted by Code2HTML, v. 0.9.1