CPython中string.find是如何实现的？

Question

我在想，字符串的'find'方法是用线性搜索实现的，还是Python用了更复杂的方式？Python的文档没有讨论具体的实现细节，所以http://docs.python.org/library/stdtypes.html对我没有帮助。有没有人能告诉我相关的源代码在哪里？

Answer 1

看起来这个算法的来源是 Boyer-Moore-Horspool 算法

Answer 2

你可以在 Objects/stringlib/find.h 这个文件里找到它，不过实际的代码是在 fastsearch.h 这个文件里。

Answer 3

关于这个实现的评论是这样的：

这是一个快速搜索和计数的实现，

它结合了Boyer-Moore算法和Horspool算法，

并且在此基础上添加了一些额外的功能。

想了解更多背景知识，可以看看这个链接： http://effbot.org/zone/stringlib.htm

—https://github.com/python/cpython/blob/master/Objects/stringlib/fastsearch.h#L5