6. (20 points) You are given two input strings: string1 and string2. You are asked to design an algorithm to execute the new TEDUCP operation with these input strings. The operation is described below: First, a low-level TEDULeftRotate operation on any string str is defined as follows: move the first character of the given string to the end, and shift all the other characters to the left. For example: if the input string is TEDU", then a single TEDULeft Rotate operation on it yields EDUT". A second left rotate of the string yields the string "DUTE. Then, the TEDUCP operation is defined as the minimum number of TEDULeft Rotate operations on string2 (Note: not on stringl) required to get the maximum-length common prefix of string1 and string2. Hint: assume that you do not have a space limitation. You may want to create a new string by concatenating some other strings, and process it. First, explain your algorithm; then write the algorithm in pseudocode, and finally discuss the computational complexity of your algorithm. Example 1: Input: string1: "TEDUniversity" string2: "SchoolOfTED" Output: Number of TEDUCP: 8 Prefix: TED Example 2: Input: string1: "UniversityOfTED" string2: "PrincetonUniversity" Output: Number of TEDUCP: 9 Prefix: University Example 3: Input: string1: "bestofbest" string2: "ofbestbest" Output: Number of TEDUCP: 6 Prefix: bestofbest