Cadena de Python ‘en’ algoritmo de implementación del operador y complejidad de tiempo

Estoy pensando en cómo implementan el operador, por ejemplo.

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

En CPython, ¿qué algoritmo se usa para implementar la concordancia de cadenas y cuál es la complejidad del tiempo? ¿Hay algún documento oficial o wiki sobre esto?

Es una combinación de Boyer-Moore y Horspool .

Puedes ver el código C aquí :

Rápida implementación de búsqueda / conteo, basada en una mezcla entre Boyer-Moore y Horspool, con algunas campanas y silbidos más en la parte superior. Para obtener más información, consulte: http://effbot.org/zone/stringlib.htm .

Desde el enlace de arriba:

Al diseñar el nuevo algoritmo, utilicé las siguientes restricciones:

  • debe ser más rápido que el algoritmo de fuerza bruta actual para todos los casos de prueba (según el código de la vida real), incluida la prueba de peor caso de Jim Hugunin
  • pequeña sobrecarga de configuración; sin asignación dinámica en la ruta rápida (O (m) para la velocidad, O (1) para el almacenamiento)
  • Comportamiento de búsqueda sublineal en buenos casos (O (n / m))
  • no peor que el algoritmo actual en el peor de los casos (O (nm))
  • debería funcionar bien tanto para cadenas de 8 bits como para cadenas de Unicode de 16 bits o de 32 bits (sin dependencias O (σ))
  • muchas búsquedas de la vida real deberían ser buenas, muy pocas deberían ser, en el peor de los casos, una implementación razonablemente simple