Fast search/count implementation, based on a mix between Boyer-Moore and Horspool, with a few more bells and whistles on the top. For some more background, see: http://effbot.org/zone/stringlib.htm.
从上面的链接:
When designing the new algorithm, I used the following constraints:
should be faster than the current brute-force algorithm for all test cases (based on real-life code), including Jim Hugunin’s worst-case test
small setup overhead; no dynamic allocation in the fast path (O(m) for speed, O(1) for storage)
sublinear search behaviour in good cases (O(n/m))
no worse than the current algorithm in worst case (O(nm))
should work well for both 8-bit strings and 16-bit or 32-bit Unicode strings (no O(σ) dependencies)
many real-life searches should be good, very few should be worst case
reasonably simple implementation
它是Boyer-Moore和Horspool的组合。
您可以查看C代码here:
从上面的链接:
相关问题 更多 >
编程相关推荐