Python chuỗi 'trong' thi hành thuật toán và thời gian phức tạp

Question

Tôi đang nghĩ đến việc làm thế nào các nhà điều hành in thực hiện, ví dụ

>>> s1 = 'abcdef' 
>>> s2 = 'bcd' 
>>> s2 in s1 
True 

Trong CPython, mà thuật toán được sử dụng để thực hiện các trận đấu chuỗi, và những gì là thời gian phức tạp? Có bất kỳ tài liệu hoặc wiki chính thức nào về vấn đề này không?

Answer 1

Đó là sự kết hợp của Boyer-Moore và Horspool.

Bạn có thể xem mã C here:

nhanh tìm kiếm/đếm thực hiện, dựa trên sự kết hợp giữa Boyer-Moore và Horspool, với một vài chi tiết chuông và còi trên đầu. Để biết thêm thông tin cơ bản, hãy xem: http://effbot.org/zone/stringlib.htm.

Từ liên kết ở trên:

Khi thiết kế các thuật toán mới, tôi đã sử dụng những hạn chế sau:

• nên nhanh hơn so với thuật toán brute-force hiện hành đối với tất cả các trường hợp thử nghiệm (dựa trên mã thực tế), bao gồm kiểm tra trường hợp xấu nhất của Jim Hugunin
• chi phí thiết lập nhỏ; không có phân bổ động trong đường dẫn nhanh (O (m) cho tốc độ, O (1) để lưu trữ)
• hành vi tìm kiếm cận tuyến trong trường hợp tốt (O (n/m))
• không tồi tệ hơn thuật toán hiện tại case (O (nm))
• sẽ hoạt động tốt cho cả chuỗi 8 bit và chuỗi Unicode 16 bit hoặc 32 bit (không phụ thuộc O (σ))
• nhiều tìm kiếm thực tế phải tốt, rất ít nhất là trường hợp xấu nhất triển khai đơn giản hợp lý