Алгоритм метода count в Python 3

Для стандартной реализации интерпретатора Python, т.е. CPython, , верно следующее:

Для поиска количества вхождений паттерна в строку используется . Так как count возвращает количество неперекрывающихся вхождений подстроки в строку, то сложность работы алгоритма Бойера — Мура будет составлять O(n + m), где n + m — это сумма длин строки и паттерна.

Я не очень хорошо разбираюсь в структуре исходного кода CPython, но очень похоже, что метод count действительно описан в файле , приведённом . Функция, описанная в нём, содержит единственный вызов -- вызов функции FASTSEARCH, описание которой я нашёл в файле , которая содержит вариант алгоритма Бойера — Мура.

Источники: