(1) Suppose that all characters in the pattern P are different. Show how to acce

Question

(1) Suppose that all characters in the pattern P are different. Show how to accelerate Brute Force Pattern Match Algorithm to run in time O(n) on an n-character text T.

(2) How many character comparisons will be Boyer-Moore algorithm make in searching for each of the following patterns in the binary text of 1000 zeros?

         (a) 00001 (b) 01111 (c) 01010

(3)

i.compute the prefix function in Knuth-Morris-Pratt Algorithm pattern match algorithm for pattern

ababbabbabbababbabb when the alphabet is ?={a,b}.

ii.How many character comparisons will be KMP pattern match algorithm make in searching for each of the following patterns in the binary text?

a. Text : repeat '' 010011" 20 items

b. Pattern : (a) 010010 (b) 010110

(4) Implement Brute Force, Boyer-Moore, and Knuth-Morris-Pratt Algorithm pattern match algorithm, and search all matches for pattern 0101 from the text of a random binary string with length 10000.

Explanation / Answer

I will answer it little later.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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