Комментарии 57
Я не понимаю, почему в таблице в разделе "Переходим к трюку" на позиции 6 (там где '@') стоит 3, а на позиции 8 стоит 5 как будто там найдено совпадение. Нет ли там ошибки?
Конечно, реально редко встретишь образец длиной 100, но в олимпиадных задачах «на поиск» это обычное дело, поэтому там простой поиск часто не подходит.
Я вас огорчу. Вокруг таких реальных задач вся биоинформатика крутиться. Там масса алгоритмов разработано именно для анализа строк ДНК.
Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
Префикс-функция, о которой велась речь в статье, выстраивает конечный автомат, по которому движется алгоритм при поиске подстроки. Это позволяет переложить такой алгоритм на ASIC/FPGA и сферу применения — intrusion detection systems, где данных много, да еще и хранить их для дальнейшего анализа не всегда возможно.
В результате расчет значений массива занимает время порядка О(длина строки).
А где доказательство?
А почему «чудо»? Потому что, он вроде как решает совсем другую задачу и это решение, после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку.
Почему задача, которую он решает, названа "вроде как совсем другой", если это прямое обобщение исходной задачи?
Для нахождения образца ааbаа в строке ааbааbааааbааbаааb склеим образец со строкой вот так ааbаа@ааbааbааааbааbаааb и вызовем для нее префикс-функцию для заполнения массива.
… и сразу же повысим требования по памяти в несколько раз! Дополнительной памяти правильная реализация алгоритма требует O(N), где N — длина образца. Ваш же способ требует O(N+M) дополнительной памяти, где N — длина образца, M — длина текста.
Там, вероятно, и вовсе нет задач где можно так запросто упереться в ограничения, особенно при работе с текстом. Но привычка совершать лишние действия может тяжело аукнуться при попытке решения какого-нибудь "гроба".
Я, наверное, вас не так понял. Вам ссылку на задачу надо или на алгоритм? Если второе — то вот: https://ideone.com/qmNQ39
'\0'
на конце образца)Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
В чем проблема вместо вывода в cout
делать что-то еще?
Или вы имеете в виду, что в данной реализации алгоритма не хватает выделения самого алгоритма? Тогда можно сделать вот так: https://ideone.com/zn9Fe4
Или вот так: https://ideone.com/pnafkx
Или еще кучей других способов. Алгоритм от этого не изменится, это лишь оформление.
Ну а если встретится задачка, где будут жесткие ограничения по памяти и скорости — так я добавил в статью процедуру prefix_find, которой нужен буфер только под образец.
В результате расчет значений массива занимает время порядка О(длина строки).
В худшем случае это S = sum(ln k, 1, n) и это не линейное время так как предел lim S/n видимо бесконечный.
Э… там вообще-то и в худшем случае линейное время, просто автор поста не стал это доказывать.
Мы не можем уменьшать текущий префикс большее число раз, чем увеличивали. А увеличиваем мы его только на 1 и не чаще 1 раз на символ из текста и шаблона. Отсюда и оценка времени O(N+M)
(Если первый символ в КМП не совпадает, мы всегда смещаемся на единицу, если последний символ в БМ не совпадает, и этого символа нет в образце — мы смещаемся сразу на длину образца! И даже если есть одинаковые символы, мы почти всегда смещаемся больше, чем на единицу).
Кстати, теперь я понимаю, почему вы не любите алгоритм Бойера-Мура — вы не считаете, что он существенно быстрее в большинстве случаев :) А, между тем, в grep используется именно Бойер-Мур, и именно из-за его более высокой скорости.
Объяснение ваше в посте про БМ некорректное. БМ тем медленнее, чем больше частичных совпадений между концом образца и текстом, а не внутри образца. Но его можно улучшить, чтобы этого замедления не было, и тогда худшая оценка будет совпадать к КМП. Получится как с быстрой сортировкой против сортировки вставками.
Поскольку редко кто в 2016м году подобные алгоритмы программирует сам вручную, я бы не рекомендовал на практике КМП, а рекомендовал БМ или Ахо-Карасика.
А для знакомства с алгоритмами рекомендовал бы Кормана вместо Хабрахабра :)
Кхм, вообще-то алгоритм Ахо-Карасика решает другую задачу, его с КМП и БМ сравнимать некорректно.
Вообще-то, алгоритм Ахо-Корасика — это и есть КМП, расширенный на насколько образцов :)
но вы же сами ниже говорите про то, как легко КМП расширяется на несколько шаблонов. Вот вместо этого лучше как раз взять готовый алгоритм Ахо-Корасика
Нельзя взять алгоритм Ахо-Корасика вместо раширенного на несколько образцов КМП — потому что это один и тот же алгоритм.
Потому что, как я уже писал ранее, использовать БМ без турбосдвига нельзя.
КМП проще хеш-функции
Но подумайте вот о чём. Олимпиады — это лишь тренировка навыков скоростного программирования, а не практика написания программных продуктов.
Для написания реальных программных продуктов нельзя использовать те же самые критерии, что и для олимпиад.
Поэтому лучше брать готовые алгоритмы, упакованные в библиотеки. Конечно, крайне желательно понимать, как они работают, чтобы знать их ограничения. Спасибо вам за хорошо иллюстрированный пост, я уверен, он поможет многим разобраться, что происходит. Но лучше думайте о промышленных программистах, которые будут использовать ваш пост, как руководство к действию — а нам всем потом именно их программами придётся пользоваться…
Зато КМП легко расширяется для нескольких образцов — а алгоритм Бойера-Мура нет.
Да и сложность в худшем случае может сыграть злую шутку, поэтому без эвристики турбосдвига алгоритм Бойера-Мура лучше не использовать. А с этой эвристикой алгоритм становится намного сложнее КМП.
Почему в примере на С++ тип переменной длины и индексов size_t
, а в примере на С — int
?
l(S)
— это префикс-функция строки S
(для удобства восприятия будет считать значением функции саму строку, а не её длину, т.е. l(ababa)=aba
). Тогда:1) Все (не только самый длинный) собственные префиксы, являющиеся также и суффиксами, строки
S
— это множество l(S)
, l(l(S))
, l(l(l(S)))
… (до тех пор, пока не получим пустую строку. Будем считать, что она также является подходящим префиксо-суффиксом).2) Рассмотрим строку
Sc
(дописали в конец строки символ c
). Пусть l(Sc)=Ac
(т.к. префикс-функция является суффиксом строки, то если только это не пустая строка, то она обязана заканчиваться на с
. А
может быть пустой строкой). Тогда нетрудно понять, что A
является префиксо-суффиксом (каким-то, не факт, что самым длинным) строки S
.3) Из этих двух соображений возникает алгоритм нахождения
l(Sc)
. Будем последовательно перебирать все префиксо-суффиксы строки S
, начиная с самого наибольшего (т.е. просто будем идти по ряду l(S)
, l(l(S))
, l(l(l(S)))
...) и проверять не будет ли это также префиксо-суффиксом для строки Sc
(для этого необходимо и достаточно, чтобы символ, следующий за концом соответствующего префикса, был с
).Примеры есть в статье, доказательство асимптотики в этом комментарии выше.
Или как изменить шрифт внутри < source > Спасибо.
Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)