Chuỗi string.find được triển khai như thế nào trong CPython?

Question

Tôi đã tự hỏi nếu phương pháp 'tìm' trên chuỗi được thực hiện với một tìm kiếm tuyến tính, hoặc nếu python đã làm một cái gì đó phức tạp hơn. Tài liệu Python không thảo luận chi tiết triển khai, vì vậy http://docs.python.org/library/stdtypes.html không giúp được gì. Ai đó có thể vui lòng chỉ cho tôi mã nguồn có liên quan không?

Answer 1

Tôi cho rằng như vậy:

fast search/count implementation, based on a mix between boyer-moore and horspool, with a few more bells and whistles on the top

Answer 2

Bạn sẽ có thể tìm thấy nó trong Objects/stringlib/find.h, mặc dù mã thực sự là trong fastsearch.h.

Answer 3

Có vẻ như thuật toán được sử dụng bắt nguồn từ Boyer-Moore-Horspool algorithm