circle correct answer and explain why

information from question 1

informarion from pg 988

4. Strategy & Algorithm Modification (5 points) The strategy of the algorithm in Problem 1 is a "sliding window" strategy: 1. Match P[1..m) with a m-length substring of T[1..m] and if it succeeds print "Pattern occurs with shift" =0 2. Then slide P one character to the right along T (i.e., s=s+l) and match P[1..m] with a m-length substring of T[2..m+1] and if it succeeds print Pattern occurs with shift" 3. Repeat step 2 until s=n-m and P[1..m) is matched with a m-length substring of T[n-m+1..n) and if this match succeeds print "Pattern occurs with shift" =n-m Now, if there are no repeated characters in P, i.e., all characters in P are distinct, it is possible to do the search for p in T faster. A modified strategy that does this is given below: 1. Use a variable count to keep track of the number of characters of P that match any substring of T. Start by matching P[1..m) with the first m-length substring of T, T[1..m]. 2. If the match fails at the very first character of P, slide P one character to the right along T (i.e., update s to s+1) and then match P[1..m) with a m-length substring of T, T[S+1.. s+m]. 3. If the match succeeds fully, print "Pattern occurs with shift" . 4. If the match succeeds fully or partially, slide P count characters to the right along T (i.e., update s to stcount) and then match P[1..m] with a m-length substring of T, T[s+1.. s+m). 5. Repeat steps 2-4 until sn-m. Assume m1 and msn. Is this strategy correct? I.e., will it result in all the occurrences of Pin T being correctly identified for all valid P-strings of at least one character in which all characters are distinct and T=strings of at least as many characters as there are in P? Circle one: This strategy is correct It is incorrect Explain your answer clearly and precisely in a few sentences: Question 1: 1. Algorithm Understanding (12 points) Understand NAIVE-STRING-MATCHER algorithm on p. 988 of the text. P and T are character arrays with the first character of P&T stored in array cells of index 1. The meaning of the condition "P(1..m]==T[5+1..s+m]" in step 4 is "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 and return FALSE otherwise continue and if all character comparisons succeed then return TRUE". 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 + m) for each of the n-m + 1 possible values of s. NAIVE-STRING-MATCHER (T. P) I n = T.length 2 m = P.length 3 for s = 0 ton-m 4 if P[1..m] == T[s +1..+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 shifts. 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 na's) and the pattern a". For each of the n-m+ 1 possible values of the shifts, 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 (11-m + 1)m), which is (?) if m = n/2]. Because it requires no preprocessing, NAIVE- STRING-MATCHER's running time equals its matching time. (c) Figure 32.4 The operation of the naive string matcher for the pattern P = aab and the text T = acaabc. We can imagine the patter P as a template that we slide next to the text. (a-d) The four successive alignments tried by the naive string matcher. In cach 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 shifts = 2, shown in part (c)