Python string 'in' алгоритм реализации оператора и временная сложность

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

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

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

Ответы

Ответ 1

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

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

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

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

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

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