2. Algorithm modification (12 points)

Replace the complex array equality condition in the if statement (step 4) of the NAVE-STRING-MATCHER with a while loop so that it behaves thus: compare P[1] with T[s+1], P[2] with T[s+2],...,compare P[m] with T[s+m] and if any of these comparisons returns FALSE then quit the character comparisons immediately otherwise continue until all m characters of P have been compared. Parts of the modified algorithm is given below. Fill in the blanks:

NAVE-STRING-MATCHER-MODIFIED(T: array [1..n] of char; P: array [1..m] of char, , mn)

1 n = T.length

2. m = P.length

3. for s = 0 to nm

4. j=1

5. while j ___ m and P[___]==T[_____]

6. j = _____

7. if j == _______ then

8. print Pattern occurs with shift s

When this algorithms execution reaches step 7 within any execution of the outer for loop, the value of the variable j carries some useful information. What is it? (circle one)

A. j = The number of character comparisons P[j]==T[s+j] that succeeded during the execution of the while loop

B. j = The number of character comparisons P[j]==T[s+j] that failed during the execution of the while loop

C. j = The number of characters of P that matched the substring T[s+1..s+m]

D. j = The number of characters of P that matched the substring T[s+1..s+m] + 1

E. j = The number of characters of P that matched the substring T[s+1..s+m] 1