Комментарии 38
у Никлауса Вирта в «Алгоритмы и структуры данных» тоже неплохо описано и примеры есть на модуле или паскале.
+3
А вообще копипаста есть немного…
+8
Частично взято из лекций, переработал, отредактировал, вот что получилось…
0
Чего-то всёравно не хватает. Не мне указывать, но я бы добавил блок-схемы, какие-нибудь таблицы со сравнениями результатов работы алгоритмов. Можно сделать лучше. Удачи!
+6
Еще можно добавить что алгоритм Рабина — Карпа использует для проверки плагиата, так же что он эффективен для многострочного поиска и поиск по множество шаблонам и что нужно делать пре подготовку текста (вырезать все знаки пунктуации). Так же, что можно спокойно использовать свои хэш функции.
+1
а Вы, случайно, не проводили тесты данных алгоритмов? недавно по информатике нужно было написать КМП и Рабина-Карпа и сравнить их с наивным алгоритмом (за квадрат), и Рабин-Карп работал в 2-10 раз хуже, чем наивный:) я грешу на медленную операцию % в питоне, но как-то это не очень похоже на правду
0
Он заметил, что РК работал в 2-10 раз хуже наивного алгоритма, не смотря на то, что асимптотически сложности равны. Читайте внимательно.
0
Извините, что читаю невнимательно комментарии, но если сконцентророваться на статье я вижу слова для РК:
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).
а для КМП:
Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
и не вижу вообще нигде слов про то что то чему то асимптотически равно.
Отсюда следует вопрос, который я и задал — не напутали ли с оценкой алгоритмов?
Собственно, какова полезность алгоритма. который в худшем случае имеет квадратичную сложность по сравнению с линейной у КМП?
Рабин и Карп с бухты-барахты придумали медленный алгоритм, а преподаватели от нечего делать его преподают, так по вашему что ли?
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).
а для КМП:
Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
и не вижу вообще нигде слов про то что то чему то асимптотически равно.
Отсюда следует вопрос, который я и задал — не напутали ли с оценкой алгоритмов?
Собственно, какова полезность алгоритма. который в худшем случае имеет квадратичную сложность по сравнению с линейной у КМП?
Рабин и Карп с бухты-барахты придумали медленный алгоритм, а преподаватели от нечего делать его преподают, так по вашему что ли?
+1
А где же хеширование???
+1
Когда я учился, те же алгоритмы объясняли по этой книжке. Мне кажется, там доходчивее…
+1
это все интересно, но в современных языках данные алгоритмы встроены
-3
Это не отменяет необходимости знать их работу и применение.
+1
Можно поинтересоваться, в каких?
+1
методы substring substr contains есть в python, java…
-1
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j] ==
target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
это фрагмент метода indexOf класса String из jre.
Какие из данных алгоритмов, кроме алгоритма прямого поиска, встроены в современных языках программирования?
+1
афигеть
а я думал там КМП…
вот это они лоханулись конечно…
а я думал там КМП…
вот это они лоханулись конечно…
0
КМП требует дополнительной памяти для хранения вычисленной префикс-функции образца. Видимо, поэтому он и не вошел в стандартные библиотеки.
+1
КМП — подготовка к поиску занимает какое-то время. Выделение памяти. Как правило поисковые строки короткие с минимумом самоповторений. Линейное сравнение использует SIMD-инструкции. Строки влезают в кэш L1 — повторное сравнение быстрое. Так что на практике КМП выигрывает в специфических условиях.
0
ну функция могла бы выбирать в зависимости от длины стро и т.п. нужный алгоритм
вот memset же использует sse2
а если в процессоре нет sse2 очевидно что memset не упадет :)
вот memset же использует sse2
а если в процессоре нет sse2 очевидно что memset не упадет :)
0
Думаю, нужно еще рассмотреть алгоритм Ахо-Корасика и Укконена — там, где применяется бор. В интернете очень сложно найти их хорошее описание с доказательством работы.
0
В описании алгоритма Кнутта-Морриса-Пратта отстутсвует упоминание о префикс-функции (которая вычисляет, насколько нужно сдвинуть курсор поиска). Контр-пример для вашего описания:
ABABABCABABAB
ABABC
ABABABCABABAB
ABABC
+6
Пожалуй, имеет смысл упомянуть об http://volnitsky.com/project/str_search/. Автор утверждает, что создал самый быстрый среди существующих алгоритм поиска подстроки в строке.
0
НЛО прилетело и опубликовало эту надпись здесь
Большой список алгоритмов поиска подстроки algolist.ru/search/esearch/index.php
0
<картинка про жпег и пнг />
0
Есть же метод поиска подстроки в строке при помощи конечного автомата.
Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.
Вроде регэкспы работают именно так?
Как я помню, это очень выгодный вариант поиска в двух случаях:
1. М << N.
2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).
Поправьте, если я не прав, могу написать подробнее, если кому-то интересно.
Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.
Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.
Вроде регэкспы работают именно так?
Как я помню, это очень выгодный вариант поиска в двух случаях:
1. М << N.
2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).
Поправьте, если я не прав, могу написать подробнее, если кому-то интересно.
Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.
+1
еще наверное актуально написать про Z-функцию
0
суфиксные деревья — поиск самый быстрый
www.youtube.com/watch?v=q9bPAVSmzfA
www.youtube.com/watch?v=q9bPAVSmzfA
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмы поиска в строке