Comments 10
а чему будут равны O(n) и o(n)?
Спасибо за статью.
Спасибо за статью.
— 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
— no worse than the current algorithm in worst case (O(nm))
отсюда — effbot.org/zone/stringlib.htm
Немного визуализации....а вот за это, отдельное спасибо. Сразу понял как работает.
Отличная статья.
Как насчет utf8 и многбайтных символов?
Я не нашел других реализаций поиска специально для неоднобайтовых кодировок, так что могу предположить что они сравниваются побайтово.
Слова «STRINGLIB_BLOOM_WIDTH может принимать значения 32, 64, 128» как бы намекают нам, что речь идёт о UCS-4/8/16. UTF можно предварительно преобразовать в UCS, это всего лишь добавит O(n).
Визуализация отличная. Спасибо.
а почему бы не использовать 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>Sign up to leave a comment.
Поиск в строке. Реализация в CPython