5. Consider the pattern P = 01010 and the string S = 01000 (i.e., the string con

Question

5. Consider the pattern P = 01010 and the string S = 01000 (i.e., the string consisting of 1,000

zeros).

(a) How many character comparisons will be made by the brute force algorithm? Justify your answer.

Note: Assume the brute force algorithm shifts the pattern P by 1 as soon as a mismatch is found in a window of size m. Also, the brute force algorithm compares characters in a window from left to right.

(b) How many character comparisons will be made by Horspool's algorithm? Justify your answer.

Explanation / Answer

b)By Horspool's algorithm:

Pattern :01010

shift Table:

Algorithm will make 1 successful and 1 unsuccessful comparision.

In each trail will shift the pattern 2 positions to the right.

0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 1 0

0 1 0 1 0

0 1 0 1 0

in trial left end of pattern will aligned against the text 's character in position as 0,2,4.....994 which is 498 trials . thus total number of comparision will be c=498*2=996

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

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