Как стать автором
Обновить

Комментарии 11

1. Заголовок не соответствует содержимому. Когда я прочитал заголовок, я ожидал, что будет попытка изобретения собственного велосипеда по поиску подстроки.
В данном случае просто сравнение вариантов с сухим цитированием из учебников.

2. Статья не то чтобы совсем бесполезная, но чёт так себе.

"Двоичный алгоритм поиска подстроки" автор придумал сам. И даже дал ему собственное название. Потом много позже публикации статьи читатели рассказали ему, что на самом деле этот алгоритм изобрели еще в 1964 году. В целом там вывод в том, что не стоит пользваться тем, что тебе предложили по умолчанию, а надо думать и выбирать — и приведен конкретный алгоритм как именно выбирать.

это перевод

и? :-)

Это он не тебе, а автору родительского коммента.

Боера-Мура можно применить не через индексы, а пропуском вычисленного количества символов.
Но в случае Java вспомогательный массив на 65536 символов это жестковато.
КМП основан на конечных автоматах

Нет. Его можно написать на конечных автоматах — но есть и более простые реализации. К примеру, в приведенной вами же реализации на Scala конечного автомата нет.


Из этих двух, Бойер-Мур показал сравнимую производительность, но они оба не совместимы со стримингом (используют произвольный доступ к haystack по индексу)

Вполне совместим, просто там нужен небольшой буфер (размером с образец).

Да, Рабин-Карп точно совместим при наличии буфера.
Неизвестно случайно какая задачка в проксе решалась?
Зарегистрируйтесь на Хабре , чтобы оставить комментарий