How to become an author
Search
Write a publication
Pull to refresh

Comments 38

у Никлауса Вирта в «Алгоритмы и структуры данных» тоже неплохо описано и примеры есть на модуле или паскале.
Total votes 3: ↑3 and ↓0+3
А вообще копипаста есть немного…
Total votes 8: ↑8 and ↓0+8
Частично взято из лекций, переработал, отредактировал, вот что получилось…
Total votes 6: ↑3 and ↓30
Чего-то всёравно не хватает. Не мне указывать, но я бы добавил блок-схемы, какие-нибудь таблицы со сравнениями результатов работы алгоритмов. Можно сделать лучше. Удачи!
Total votes 6: ↑6 and ↓0+6
Спасибо за советы, в следующий раз все учту и исправлюсь.
Total votes 4: ↑2 and ↓20
Ещё не поздно дополнить этот топик.
Total votes 6: ↑6 and ↓0+6
Поддерживаю, с краткими блоксхемами и со сравнением работы алгоритмов будет намного лучше.
Total votes 3: ↑3 and ↓0+3
Еще можно добавить что алгоритм Рабина — Карпа использует для проверки плагиата, так же что он эффективен для многострочного поиска и поиск по множество шаблонам и что нужно делать пре подготовку текста (вырезать все знаки пунктуации). Так же, что можно спокойно использовать свои хэш функции.
Total votes 1: ↑1 and ↓0+1
а Вы, случайно, не проводили тесты данных алгоритмов? недавно по информатике нужно было написать КМП и Рабина-Карпа и сравнить их с наивным алгоритмом (за квадрат), и Рабин-Карп работал в 2-10 раз хуже, чем наивный:) я грешу на медленную операцию % в питоне, но как-то это не очень похоже на правду
Total votes 2: ↑1 and ↓10
Рабин-Карп на коротких образцах (меньше 20 символов) сильно проигрывает (стабильно 40 мб/с при поиске чего угодно где угодно). КМП довольно быстрый (300 мб/с при поиска «Наташа» в Войне и Мир), Бойер-Мур (300-700 мб/с), Хорспул — до 2 гб/с(!), если не синтетические тесты.
This comment wasn’t rated yet0
А вы ничего не путаете c оценкой РК?
Я, если честно, не осилил идею РК за вашей алегброй, но предположим N = 1000, M = 10 тогда в худшем случае РК намного менее шустр чем КМП, порядка О(9910) против O(1010), то есть почти в 10 раз медленее в худшем случае, как и заметил mydoom
This comment wasn’t rated yet0
Он заметил, что РК работал в 2-10 раз хуже наивного алгоритма, не смотря на то, что асимптотически сложности равны. Читайте внимательно.
This comment wasn’t rated yet0
Извините, что читаю невнимательно комментарии, но если сконцентророваться на статье я вижу слова для РК:

В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

а для КМП:

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.

и не вижу вообще нигде слов про то что то чему то асимптотически равно.

Отсюда следует вопрос, который я и задал — не напутали ли с оценкой алгоритмов?

Собственно, какова полезность алгоритма. который в худшем случае имеет квадратичную сложность по сравнению с линейной у КМП?

Рабин и Карп с бухты-барахты придумали медленный алгоритм, а преподаватели от нечего делать его преподают, так по вашему что ли?
Total votes 1: ↑1 and ↓0+1
РК, имхо, один из частичных случаев хеширования :)
This comment wasn’t rated yet0
Когда я учился, те же алгоритмы объясняли по этой книжке. Мне кажется, там доходчивее…
Total votes 1: ↑1 and ↓0+1
это все интересно, но в современных языках данные алгоритмы встроены
Total votes 3: ↑0 and ↓3-3
Это не отменяет необходимости знать их работу и применение.
Total votes 3: ↑2 and ↓1+1
в большинстве практических задач таки отменяет :)
Total votes 3: ↑0 and ↓3-3
Можно поинтересоваться, в каких?
Total votes 1: ↑1 and ↓0+1
методы substring substr contains есть в python, java…
Total votes 1: ↑0 and ↓1-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.
Какие из данных алгоритмов, кроме алгоритма прямого поиска, встроены в современных языках программирования?
Total votes 1: ↑1 and ↓0+1
афигеть
а я думал там КМП…
вот это они лоханулись конечно…
Total votes 2: ↑1 and ↓10
КМП требует дополнительной памяти для хранения вычисленной префикс-функции образца. Видимо, поэтому он и не вошел в стандартные библиотеки.
Total votes 1: ↑1 and ↓0+1
КМП — подготовка к поиску занимает какое-то время. Выделение памяти. Как правило поисковые строки короткие с минимумом самоповторений. Линейное сравнение использует SIMD-инструкции. Строки влезают в кэш L1 — повторное сравнение быстрое. Так что на практике КМП выигрывает в специфических условиях.
This comment wasn’t rated yet0
ну функция могла бы выбирать в зависимости от длины стро и т.п. нужный алгоритм
вот memset же использует sse2
а если в процессоре нет sse2 очевидно что memset не упадет :)
This comment wasn’t rated yet0
В зависимости от архитектуры проще — можно выбрать при запуске программы. В зависимости от длины — замедление потенциально видимое на очень коротких строках.
This comment wasn’t rated yet0
Думаю, нужно еще рассмотреть алгоритм Ахо-Корасика и Укконена — там, где применяется бор. В интернете очень сложно найти их хорошее описание с доказательством работы.
This comment wasn’t rated yet0
В описании алгоритма Кнутта-Морриса-Пратта отстутсвует упоминание о префикс-функции (которая вычисляет, насколько нужно сдвинуть курсор поиска). Контр-пример для вашего описания:

ABABABCABABAB
ABABC
Total votes 6: ↑6 and ↓0+6
Пожалуй, имеет смысл упомянуть об http://volnitsky.com/project/str_search/. Автор утверждает, что создал самый быстрый среди существующих алгоритм поиска подстроки в строке.
This comment wasn’t rated yet0
UFO just landed and posted this here
Есть же метод поиска подстроки в строке при помощи конечного автомата.
Там, безусловно, тратится время и память на построение непосредственно автомата, если мне не изменяет память надо М*М операций (М — длина искомой строки), после чего поиск происходит линейно.
Т.е. общая сложность, если не считать дополнительные расходы по памяти, получается М*М + N.

Вроде регэкспы работают именно так?

Как я помню, это очень выгодный вариант поиска в двух случаях:

1. М << N.
2. Он легко адаптируется к поиску К подстрок в строке N, почти без дополнительных телодвижений (усложняется лишь этап построения автомата).

Поправьте, если я не прав, могу написать подробнее, если кому-то интересно.

Самому пришлось как-то искать порядка 50ти фиксированных и известных заранее подстрок в большом потоке, и именно это решение для меня оказалось оптимальным, т.к. однажды просчитав автомат я его сохранил для дальнейшего использования.
Total votes 1: ↑1 and ↓0+1
еще наверное актуально написать про Z-функцию
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr