DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 853

Q UIZ

Answer the quiz for this chapter online at www.cs.armstrong.edu/liang/intro10e/test.html .

P ROGRAMMING E XERCISES
*22.1

( Maximum consecutive increasingly ordered substring ) Write a program that
prompts the user to enter a string and displays the maximum consecutive
increasingly ordered substring. Analyze the time complexity of your program.
Here is a sample run:

Enter a string:abcabcdgabxy
abcdg

Enter a string: abcabcdgabmnsxy
abmnsxy

**22.2

( Maximum increasingly ordered subsequence ) Write a program that prompts
the user to enter a string and displays the maximum increasingly ordered sub-
sequence of characters. Analyze the time complexity of your program. Here is
a sample run:

Enter a string: Welcome
Welo

*22.3

( Pattern matching ) Write a program that prompts the user to enter two strings
and tests whether the second string is a substring of the first string. Suppose
the neighboring characters in the string are distinct. (Don't use the indexOf
method in the String class.) Analyze the time complexity of your algorithm.
Your algorithm needs to be at least O(n) time. Here is a sample run of the
program:

Enter a string s1: Welcome to Java
Enter a string s2: come
matched at index 3

*22.4

( Pattern matching ) Write a program that prompts the user to enter two strings
and tests whether the second string is a substring of the first string. (Don't use
the indexOf method in the String class.) Analyze the time complexity of
your algorithm. Here is a sample run of the program:

Enter a string s1: Mississippi
Enter a string s2: sip
matched at index 6