Python строка «в» реализации оператора алгоритма и временной сложности

Question

Я имею в виду, как оператор in реализовать, например

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

В CPython, какой алгоритм используется для реализации сопоставления данных, и что это временная сложность? Есть ли официальный документ или wiki об этом?

Answer 1

Это комбинация Boyer-Moore и Horspool.

Вы можете просмотреть код C here:

Быстрой реализация поиска/счетов, на основе сочетания между Бойер-Муром и Horspool, еще с несколькими прибамбасами на вершине. Для получения дополнительной информации см.: http://effbot.org/zone/stringlib.htm.

Из приведенной выше ссылке:

При разработке нового алгоритма, я использовал следующие ограничения:

• должен быть быстрее, чем текущий алгоритм перебора всех тестовых случаев (основанный на реальном коде), включая худший случай Джима Хьюгунина
• небольшие накладные расходы; нет динамического распределения в быстром пути (O (m) для скорости, O (1) для хранения)
• Сублинейное поведение поиска в хороших случаях (O (н/м))
• не хуже, чем текущий алгоритм в худшем case (O (nm))
• должен хорошо работать как для 8-разрядных строк, так и для 16-разрядных или 32-разрядных строк Unicode (без зависимостей O (σ))
• много реальных поисков должно быть хорошим, очень мало должно быть худшим случаем достаточно простая реализация