JAVA

Consider the problem of counting, in a given text, the number of substrings that start with an and end with a . For example, there are four such substrings in CGHABDFGAGHAHGHBS. Assume all input and output is in upper case.

1. Design a brute-force algorithm for this problem and determine its efficiency class (order of growth). Implement a method to do this and a main method to run the program.

2. Design and implement a more efficient algorithm for this problem as a method and invoke it from the same main program as written above.

In implementing your program, read in the input as shown (the first line is the string, the second line is the starting substring, and the third line is the second substring:

SAMPLE INPUT:

 CGHABDFGAGHAHGHBS A B 

Your output will consist of a single integer, displaying the number of substrings: SAMPLE OUTPUT:

4