Coincidentally, I was investigating a slightly more general version of that question last week, and I found this paper getting a 3× speedup, and more on parallel machines: <a href="http:&#x2F;&#x2F;research.microsoft.com&#x2F;pubs&#x2F;208237&#x2F;asplos302-mytkowicz.pdf" rel="nofollow">http:&#x2F;&#x2F;research.microsoft.com&#x2F;pubs&#x2F;208237&#x2F;asplos302-mytkowic...</a><p>The summary is that once you&#x27;ve computed the KMP state transition function, you compute its prefix sum under composition and then ask at which textual indices it assumes a final state.  This abstract description of the KMP algorithm is sufficiently general to cover realizations with different time and space complexity, including not just the purely serial uniprocessor O(N)-time constant-space realization, but also potentially the 3× efficient SIMD realization described in the paper, efficient O(log N)-time parallel realizations and GPGPU realizations; and it is sufficiently specific to automatically derive an efficient realization.<p>An even more interesting question, to me, is what kind of formalism would make it easy to rigorously (and perhaps even automatically) derive KMP and&#x2F;or BM from the abstract definition of the string search problem and an objective of reducing computation time.