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+1) 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" = nm 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. updates 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., updates to sucount) and then match P[1..m] with a m-length substring of T, T[s+1.. Sum). 5. Repeat steps 2-4 until s>n-m. Assume m21 and msn. Is this strategy correct? I.e., will it result in all the occurrences of P in 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: 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+1) 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" = nm 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. updates 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., updates to sucount) and then match P[1..m] with a m-length substring of T, T[s+1.. Sum). 5. Repeat steps 2-4 until s>n-m. Assume m21 and msn. Is this strategy correct? I.e., will it result in all the occurrences of P in 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