Problem A: (A Type of) Sequence Matching (20 points)

One string analysis task that played a crucial role in mapping the human genome is the following: given two strings s1 and s2, find the largest substring occurring at both the very beginning of s1 and the very end of s2. For example, if s1 is the string ACTTTCTAT ands2 is the string TGTGTTTTGAAAAAACT, notice that ACT occurs at the beginning of s1 and the end of s2. Moreover, no longer substring occurring at the beginning of s1 also occurs at the end of s2: for example, the first four characters of s1, namely ACTT, are not the final four characters of s2; the first five characters of s1, namely ACTTT, are not the final five characters of s2; and so on.

Write a C++ program that does the following:

Asks the user to input the two strings s1 and s2.

Finds the longest substring that occurs both at the beginning of s1 and the end ofs2.

Prints out that substring and its length.

Has a continuation loop, so the user can repeat the above steps as many times as he or she likes.

Here are additional comments and requirements:

Do not make any assumptions about the strings lengths. In particular, the two strings might have different lengths.

Your program should store the strings as C++-style strings.

You may use any of the string class functions mentioned in the textbook.

Your solution should not be a long program, but think carefully about the program logic.

Here is some example output.

1

Input 2 strings: ACTTACT ACTG Longest match: Match length: 0 Input 2 more strings? (y/n) y Input 2 strings: 

ACTG ACTTACT Longest match: ACT Match length: 3 Input 2 more strings? (y/n) y Input 2 strings: ACTTCATTCA GTGCACGACTTCATT Longest match: ACTTCATT Match length: 8 Input 2 more strings? (y/n) n 

As usual, follow the input/output format shown in the example.

Problem B: Continued Fractions

A continued fraction representation of a number is a representationc0 +(1/c1 +(1/c2 +(1/c3 +...(1/cn?1)...))).

For example,

1 + 1 = 1.428571.2+1

3

Write a program that does the following:

Asks a user to input a size n, and then input the numbers c0, . . . , cn?1. The program

should store the ci in an integer array.

Use a recursive function (see below) to compute the continued fraction for those

numbers.

Print the value of the continued fraction, with 12 digits to the right of the decimal point.

All these steps should be within a continuation loop so the user can input and compute a number of continued fractions.

To compute the continued fraction, write a recursive function continuedFraction. You will need to decide what the parameters and return type for this function will be.

Here is an example of program input/output: 2

Input number of values (max. of 100): 1 Input values: 4 Value of continued fraction: 4.000000000000 Input another continued fraction (y/n)? y Input number of values (max. of 100): 3 Input values: 1 2 3 

Value of continued fraction: 1.428571428571 Input another continued fraction (y/n)? y Input number of values (max. of 100): 8 Input values: 3 7 15 1 292 1 1 1 

Value of continued fraction: 3.141592653619 Input another continued fraction (y/n)? n 

As usual, follow the input/output format shown in the example.