Описание работы алгоритма Shift-OR для поиска подстроки в строке

[@alexxz]

Правильно ли я понимаю, что этот алгоритм ничем не лучше наивного сравнения? Если так, то для чего он нужен?

[@alexxz]

Пардон, не сразу понял, что речь идёт про нечёткий поиск.

[@lightcaster]

На сколько я знаю, есть два варианта алгоритма — один для четкого, другой для нечеткого поиска.

На практике работает довольно быстро. Выигрыш достигается за счет побитовых операций.

[@aisek]

Что-то не совсем понятно, в чем преимущество перед префикс-функцией. Ну разве что для паттернов короче 64 символов может быть будет чуть быстрее.

[@susl]

Он достаточно быстр, если искомое слово влазит в машинное слово (простите за каламбур), работаем с маленьким алфавитом (ASCII, например) и имеем большой текст в котором нужно искать.

[@lightcaster]

Спасибо, хорошая статья.

[@agorkov]

Не совсем понятно, как находить частичные совпадения, если Вы предлагаете хранить только два столбца. Разве при этом информация не теряется?

[@tltshnik]

Не совсем понял вопроса. Например, на этой картинке:

если у нас есть только 8 столбец, то по нему мы можем определить, что на данном символе (8 в T) заканчивается совпадение первых 4 символов из P (т.к. в 4 строке стоит единица). То есть у нас совпали предыдущие 4 символа.

Или я не правильно понял, что Вы имеете ввиду?

[@eZyatev]

Ув. tltshnik, ссылки на источники информации в завершающей части статьи оформляйте аккуратнее. Сайт поисковой системы, на который Вы указываете, — слишком всеобъемлющий источник.

[@bolk]

Ваша ссылка вообще никуда не ведёт.

[@maovrn]

Список используемой литературы:
— Библиотека им. Ленина

Удобно для дипломников. Наверняка что-нибудь найдется.

[@tltshnik]

Обязательно учту при написании других постов.

[@YourChief]

похоже на репост учебника по СиАОДу третьего курса. раз автор не удосужился, я накидаю ссылок: Виктор Дмитриевич Колдаев «Алгоритмы и структуры данных». я у него учился, да. алсо, автор забыл указать что для частных случаев функция сложности этого алгоритма квадратичная, поэтому его оценка сложности неверная. вычислять эти сдвиги побитово очень плохо, да и вообще есть гораздо более простой алгоритм, где просто так же передвигаем окно с шагом в 1 байт и добавляем к контрольной сумме байт, входящий в окно и вычитаем байт, покидающий окно и на каждом шаге просто сравнимаем контрольную сумму окна и образца.

[@YourChief]

кому интересно — в книжке выше есть так же алгоритм кнута-морриса-пратта и другие алгоритмы поиска с гарантированным временем O(n). правда насчёт редакции книжки подсказать не могу, но наверняка в последней всё есть

[@YourChief]

насчёт функции сложности прошу прощения — всё верно указано

[@tltshnik]

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