Comments 11
1. Заголовок не соответствует содержимому. Когда я прочитал заголовок, я ожидал, что будет попытка изобретения собственного велосипеда по поиску подстроки.
В данном случае просто сравнение вариантов с сухим цитированием из учебников.
2. Статья не то чтобы совсем бесполезная, но чёт так себе.
В данном случае просто сравнение вариантов с сухим цитированием из учебников.
2. Статья не то чтобы совсем бесполезная, но чёт так себе.
+16
"Двоичный алгоритм поиска подстроки" автор придумал сам. И даже дал ему собственное название. Потом много позже публикации статьи читатели рассказали ему, что на самом деле этот алгоритм изобрели еще в 1964 году. В целом там вывод в том, что не стоит пользваться тем, что тебе предложили по умолчанию, а надо думать и выбирать — и приведен конкретный алгоритм как именно выбирать.
+3
я просто оставлю это здесь, предлагаю автору попытаться побить бенчмарк в статье внизу
0x80.pl/articles/simd-strfind.html
0x80.pl/articles/simd-strfind.html
+4
Боера-Мура можно применить не через индексы, а пропуском вычисленного количества символов.
Но в случае Java вспомогательный массив на 65536 символов это жестковато.
Но в случае Java вспомогательный массив на 65536 символов это жестковато.
+1
КМП основан на конечных автоматах
Нет. Его можно написать на конечных автоматах — но есть и более простые реализации. К примеру, в приведенной вами же реализации на Scala конечного автомата нет.
Из этих двух, Бойер-Мур показал сравнимую производительность, но они оба не совместимы со стримингом (используют произвольный доступ к haystack по индексу)
Вполне совместим, просто там нужен небольшой буфер (размером с образец).
+2
del
+1
Неизвестно случайно какая задачка в проксе решалась?
0
Sign up to leave a comment.
Пишем поиск подстроки лучше, чем в учебниках