Algorithm question! need help!

1. Generalize the pseudocode of Rabin-Karp's string matching algorithm (Algorithm RABIN-KARP in Lecture 9) to make it able to search for more than one specified pattern. You may assume that the input consists of a target string T of length n, a set P = {P1,P2,.., Pk} of pattern strings with |P1| = |P2 : can only make one pass over T. The output should be a list of statements of the form Pattern number j occurs with shift s" that specifies all occurrences in T of strings from P. |PR| = m, and the parameters d and q. The length-m sliding window %3D (2 marks) The Rabin-Karp Algorithm "A randomized algorithm for the Exact String Matching Problem (Las Vegas type). 1 Strategy: 1 Calculate a hash value p for the pattern string - For each length-m substring T' of T, calculate the hash value of T'. If p is equal to the hash value of T', apply the naive string matching algorithm to verify if indeed P =T' (if so, output this shift). - Define the hash function using number theory so that given the hash value of T[(s+1)..(s+ m)], the hash value of T[(s+2)..(s+ m+1)] can be computed efficiently. = A "sliding window" technique. PART II The Rabin-Karp Algorithm - Interpret every length-m string S as an m-digit number in base d, where d is the size of the alphabet. Let g be a large prime number (usually chosen so that dq just fits within one machine word). Define the hash value of S as: h(S) =E S[m i] d' (mod q) i3D0 Then: h(T[(s+2)..(s+ m+1)]) = ((h(T[(s+1)..(s+ m)]) T[s+1] - dm-1).d+T[s+m+1]) (mod q) 22 / 41 23 / 41 COMP3011 Lecture 9 COMP3011 Lecture 9 The Rabin-Karp Algorithm, pseudocode The Rabin-Karp Algorithm, example RABIN-KARP(T, P,n,m, d,q) h = dm-1 mod a P: mod 13 I/ preprocessing for i = 1 to m p = (d .p+ Pli)) mod g to = (d to + T[i]) mod q for s = 0 ton - m I 2 3 4 S67 89 10 II 12 13 14 IS 16 17 IR 19 2 3 59 0 2 3 1 415 2 6 7 39 9 2I T: I/ matching if p == t, if P[1..m] == T[s +1..s + m] print "Pattern occurs with shift" s mod 13 ... ... 89 3 11017 8 45 10 11 79 11 spurious hit valid if s