Suppose we want to find the first occurrence of a string P1P2 ...Pk in a long in

Question

Suppose we want to find the first occurrence of a string P1P2 ...Pk in a long input string A1A2 ...AN . We can solve this problem by hashing the pattern string, obtaining a hash value Hp, and comparing this value with the hash value formed from A1A2 ...AN ,A2A3 ...Ak+1,A3A4 ...Ak+2, and so on until AN?k+1AN?k+2 ...AN . If we have a match of hash values, we compare the strings character by character to verify the match. We return the position (in A) if the strings match, and we continue in the unlikely event that the match is false. a. Show that if the hash value of AiAi+1 ...Ai+k?1 is known then the hash value of Ai+1Ai+2 ...Ai+k can be computed in constant time. b. Show that the running time is O(k + N) plus the time spent refuting false matches.

Explanation / Answer

hash for AiAi+1 ...Ai+k is known. let it be called H suppose the hash is a linear function like addition of ascii values to calculate hash for Ai+1Ai+2 ...Ai+k we have to subtract ascii of Ai from H That is a constant time operation. For finding a match you have to each time calculate the hash by shifting letter by letter until you find a match. plus in the starting you will calculate the hash for A1A2A3...Ak which wil take linear time O(k) therefore adding together we will ahve O(k+n) time

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.