3. Algorithm Correctness (10 points)

A different modification of NAVE-STRING-MATCHER the effectively implements the same strategy is given below. But it is an incorrect algorithms.

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

1 n = T.length

2 m = P.length

3 s = 0

4 while s

5 for i = 1 to m

6 if P[i] != T[s+i] then

7 s = s+i

8 exit the i-loop and go to step 4

9 print "pattern occurs with shift" s

10 s = s+m

Prove by Counterexample that it is incorrect by providing a problem instance for which it fails and explaining why it fails (complete the parts of the proof below).

Problem Instance:

P=

T=

Correct answer or answers (correct values of shift s):

The value or values of s that the algorithm will print:

Brief and precise explanation of why the algorithm prints incorrect answers for the given problem instance:

32.1 The naive string-matching algorithm The naive algorithm finds all valid shifts using a loop that checks the condition P [1 . . m] = T[s + 1 . . s + ml for each of the n-m + 1 possible values of s NAIVE-STRING-MATCHER (T, P) I n- T.length m= P.length 3 for s0 to n-m print "Pattern occurs with shift" s Figure 32.4 portrays the naive string-matching procedure as sliding a "template" containing the pattern over the text, noting for which shifts all of the characters on the template equal the corresponding characters in the text. The for loop of lines 3-5 considers each possible shift explicitly. The test in line 4 determines whether the current shift is valid; this test implicitly loops to check corresponding character positions until all positions match successfully or a mismatch is found Line 5 prints out each valid shift s. Procedure NAIVE-STRING-MATCHER takes time O((n - m + 1)m), and this bound is tight in the worst case. For example, consider the text string a" (a string of n a's) and the pattern a. For each of the-1 possible values of the shift s, the implicit loop on line 4 to compare corresponding characters must execute m times to validate the shift. The worst-case running time is thus ((n-m + 1)m), which is (n*) if m-In/2]. Because it requires no preprocessing, NAIVE- STRING-MATCHER's running time equals its matching time S_ a lab Figure 32.4 The operation of the naive string matcher for the pattern Paab and the text T = acaabe, we can imagine the pattern P as a template that we slide next to the text. (a-d) The four successive alignments tried by the naive string matcher. In each part, vertical lines connect cor- responding regions found to match (shown shaded), and a jagged line connects the first mismatched character found, if any. The algorithm finds one occurrence of the pattern, at shift2, shown in part (c)