Поиск в строке. Реализация в CPython

[aNDREIQA]

а чему будут равны O(n) и o(n)?
Спасибо за статью.

[leron]

— sublinear search behaviour in good cases (O(n/m))
— no worse than the current algorithm in worst case (O(nm))

отсюда — effbot.org/zone/stringlib.htm

[Dark_MX]

Немного визуализации....

а вот за это, отдельное спасибо. Сразу понял как работает.

[mrjj]

Отличная статья.

[el777]

Как насчет utf8 и многбайтных символов?

[leron]

Я не нашел других реализаций поиска специально для неоднобайтовых кодировок, так что могу предположить что они сравниваются побайтово.

[cblp]

Слова «STRINGLIB_BLOOM_WIDTH может принимать значения 32, 64, 128» как бы намекают нам, что речь идёт о UCS-4/8/16. UTF можно предварительно преобразовать в UCS, это всего лишь добавит O(n).

[valzevul]

Визуализация отличная. Спасибо.

[GabrielViolet]

а почему бы не использовать difflib?
Пример велосипеда по поиску общей подстроки для двух строк

def get_subline(str_first, srt_second):
    s = difflib.SequenceMatcher(None, str_first, srt_second)
    match = s.find_longest_match(0, len(str_first), 0, len(srt_second))
    return str_first[match[0]:match[0]+match[2]].strip()
</python>