Я думаю о том, как реализуется оператор in, например
>>> s1 = 'abcdef'
>>> s2 = 'bcd'
>>> s2 in s1
True
В CPython, какой алгоритм используется для реализации соответствия строк, и какова временная сложность? Есть ли официальный документ или вики об этом?
Это комбинация Boyer-Moore и Horspool.
Вы можете просмотреть код C здесь:
Быстрая реализация поиска/подсчета, основанная на смеси между Бойер-Муром и Хорспулом, с еще несколькими колокольчиками и свистами на вершине. Для получения дополнительной информации см. Раздел http://effbot.org/zone/stringlib.htm.
Из приведенной выше ссылки:
При разработке нового алгоритма я использовал следующие ограничения:
- должен быть быстрее, чем текущий алгоритм грубой силы для всех тестовых случаев (основанный на реальном коде), включая худший случай с Джим Хьюгунином
- небольшие накладные расходы; нет динамического распределения в быстром пути (O (m) для скорости, O (1) для хранения)
- сублинейное поведение поиска в хороших случаях (O (n/m))
- не хуже текущего алгоритма в худшем случае (O (nm))
- должен хорошо работать как для 8-битных строк, так и для 16-разрядных или 32-разрядных строк Unicode (без зависимостей O (σ))
- многие поиски в реальной жизни должны быть хорошими, очень немногие должны быть в худшем случае разумно простая реализация