• replace("cat", "dog", "My cat is named Muffy") = "My dog is named Muffy"
• replace("man", "person", "Upper management") = "Upper personagement"

Notice that the string being replaced does not have to be a word. It can be anywhere, including in the middle of a word.

If x does not occur in s at all, then replace(x, y, s) should yield s. For example,

• replace("cat", "dog", "upper management") = "upper management".

Functions often use other functions to help them. You will write a helper function that makes writing replace(x, y, s) easier.

1. Write a definition of function indexOf(x, s), which yields the position where the first occurrence of x starts in s. If x does not occur in s, then indexOf(x, y) should yield 0. For example,

   • indexOf("bcd", "abcdefg") = 2 (since "bcd" occurs in "abcdefg" starting at the second character)

   • indexof("defg", "abcdefg") = 4 (since "defg" occurs in "abcdefg" starting at the fourth character)

   • indexof("cab", "abcdefg") = 0 (since "cab" does not occur in "abcdefg")

   Use a loop to search for the first position where x occurs in s. Notice that x occurs in s at position n if x == s_*[n, ..., n + length(x) - 1].

   Write an Execute part that tests your indexOf function. Try it on at least one case where the string occurs and one where it does not. Also test indexOf("a", "a"). When indexOf appears to work, continue to the next step.

2. Write a definition of replace(x, y, s). Use indexOf to find the position where x occurs in s (or whether it occurs at all). Then build the result string by concatenating the part before the first occurrences of x with y and the part that occurs after the first occurrence of x. Think about how to find the parts.

   Do not compute the same thing more than once. To avoid computing something twice, give its answer a name. Then refer to that name.

3. Write an Execute part that tests your replace function. Try it on at least one case where the string to be replaced does occur in the string, and at least one case where the string to be replaced does not occur in the string. Display the results.