Алгоритмы поиска подстроки на JavaScript

[jacob1237]

Раз уж заговорили про алгоритмы поиска подстроки, предлагаю также упомянуть Ахо-Корасик, хотя он больше для поиска сразу нескольких подстрок одновременно.

[mayorovp]

Ахо-Корасик — это тривиальное обобщение КМП на несколько образцов

[IraidaLakstegal]

и привел примеры скорости работы:

автор был бы молодцом если бы показал эти результаты в статье

[Nyppy]

Я не ставил цель измерить скорость работы (хотя хотел). Но думаю в будущем попробую заняться сравнением скорости алгоритмов на разных данных. Спасибо

[kovserg]

if (i === str.length && j !== searchString.length)

Накой это условие? Если оно всегда верно.

[Coler95]

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

[Nyppy]

На фронте такое мало где используется, в основном такие алгоритмы размещаются на бэке. Но я лично впервые столкнулся с такой задачей на leetcode

[a-ilin]

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

[anapogo]

Мне кажется Вы пошли по "сложному" пути...

Возможно понятие "Регулярное выражение" упростит задачу ;-)

https://ru.stackoverflow.com/questions/457096/Регулярное-выражение-поиск-подстроки-в-строке

[Frimko]

А как вы думаете, регулярки на каком алгоритме работают в js?

[Irval]

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

[mayorovp]

Ну, ДКА построенный из регулярки вида /литерал/ совпадает с тем как ведёт себя алгоритм КМП.

Но в общем случае — да, вещи совершенно разные.

[mayorovp]

В некоторых случаях, например, при использовании простых хеш-функций, возможны ложные совпадения, которые необходимо дополнительно проверять посимвольно;

Вообще-то, Робина — Карпа только с простыми хеш-функциями и работает, поскольку для него критична возможность вычислить новую хеш-функцию за константное время.

Также хочу отметить, что КМП дает выигрыш только в случае если в таблицы префиксов есть положительные значения. Лишь в этом случае указатель будет сдвигается более чем на единицу.

Этот алгоритм "даёт выигрыш" в любом случае, поскольку работает за гарантированное линейное время. И указатель всегда сдвигается ровно на 1 независимо от таблицы префиксов.

---

А вообще, если вам требуется найти в строке подстроку в неучебных целях, используйте indexOf.

[domix32]

А где бенчмарки?