0
$\begingroup$

Consider the following claim: the pre-processing time of KMP algorithm is more efficient than the pre-processing time of Boyer-Moore algorithm, and the overall running time of KMP is rather more efficient than Boyer-Moore.

Is there an example Pattern p and text T to illustrate why one should not agree with this statement?

Improve this question
$\endgroup$
3
  • $\begingroup$ 1. "It is assumed" - who assumes that? Where does that statement come from? What makes you think one should disagree with that statement? 2. What have you tried? Have you read the analysis of the running time of these two algorithms? These two algorithms have been analyzed in great depth in the literature and in textbooks; there's little point in us repeating that information. We expect you to do a significant amount of research/self-study before asking here, and to show us what research you've done. $\endgroup$
    – D.W. ♦
    Commented Jul 8, 2016 at 15:09
  • 1
    $\begingroup$ The answer is clearly yes -- just pick a P and T that let BM achieve (or nearly achieve) its best-case performance. Since that performance will be sublinear in |T|, it will necessarily be better than what KMP could manage on the same P and T, as KMP's best-case behaviour is linear in |T|. So if you think about what kind of inputs let BM "get sublinear", you will come up with an example P and T yourself in no time. $\endgroup$
    – j_random_hacker
    Commented Jul 8, 2016 at 15:10
  • $\begingroup$ Thank you. I will try it. and sorry for the inconvenience occurred. $\endgroup$
    – dulaj sanjaya
    Commented Jul 8, 2016 at 15:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.