Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89567 Mon, 13 Oct 2003 21:07:15 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89567 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89566 Mon, 13 Oct 2003 20:30:55 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89566 Цитата Visitor, 13.10.03, 20:22:23

2 lunc: Алгоритм Бойера-Мура примерно так и делает. Только там прописаны сдвиги для каждого символа искомой подстроки


Про него я и говорил :)
Пример:

Let us consider the following example    (надо найти вхождение Override):
        Override     (совпадают символы ide)
              Override   (совпадает символ e)

В начале в текущей позиции находим первый с конца образца символ не соответствующий символу в строке (стоп-символ). Чтобы не пропустить ни одной возможной позиции сдвигаем образец вправо до первого вхождения стопового символа. Повторяем.

Описан этот алгоритм и еще несколько 9включая на конечных автоматах) в журнале Программист #6 2002 "Алгоритмы: "умный" поиск в тексте"]]> lunc Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89565 Mon, 13 Oct 2003 16:22:23 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89565 в среднем не будет работать быстрее, чем самый очевидный из уже предложенных :)

2 lunc: Алгоритм Бойера-Мура примерно так и делает. Только там прописаны сдвиги для каждого символа искомой подстроки]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89564 Mon, 13 Oct 2003 11:20:51 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89564 Самый эффективный поиск там был начиная с конца текста.
Ищешь с конца первое вхождение первого символа подстроки. При повторяющихся символах в подстроке сдвигать можно на разнице между двумя вхождениями этих символов.
По-моему так....]]> lunc Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89563 Sun, 12 Oct 2003 21:37:04 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89563
хеш будет быстрее, так как больше неправильных вариантов будут отсекаться без посимвольного сравнения. тут кстати где то рядом уже была подобная тема.

кстати простой вариант с первой буквой - этот тот же хеш. просто хеш фукнция от строки - взять первую букву.]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89562 Sun, 12 Oct 2003 17:07:24 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89562 Цитата Visitor, 12.10.03, 03:18:46
Что-то мне кажется, что етот, с хеш-функцией, алгоритм (1) будет НЕ быстрее, чем ранее предложенный алгоритм (2) (поиск первой буквы, затем сравнение остальных), в том случае, если  буквы в просматриваемом тексте распределены равномерно... Если же неравномерно, то (1) в среднем будет работать с такой же скоростью, что и (2), но у (2) будут случаи "плохих" и "хороших" искомых подстрок :)

Ясен пень, если тебе хватает первого метода, то и не нечего извращаться, просто я предлагаю другой хороший вариант.]]> Ivan_Govnoff Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89561 Sun, 12 Oct 2003 08:04:22 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89561 Sl0n Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89560 Sat, 11 Oct 2003 23:18:46 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89560
Самым быстрым, вроде, считают алгоритм Бойера-Мура, но его еффективность проявляется только при значительной длине искомой подстроки.]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89559 Sat, 11 Oct 2003 22:16:12 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89559
1.
Считаем хэш-функцию типа H(s) = s[0] + s[1] + ... + s[n-1], где s - подстрока длиной n, которую нужно найти. Вместо + можно взять xor или что-нибудь еще.

2.
Считаем значение хэш-функции для первых n символов строки S в которой ведется поиск.

3. i = n;

4.
Если H совпадает с H(s), проверяем посимвольным сравнением и делаем выводы, если нет - идем дальше:
H = H - S[i-n] + S[i]; i++;

5. Goto 4

Т.е. фишка в том, что мы не пересчитываем каждый раз значение хэша заново, а вычисляем его из предыдущего всего за две быстрые операции (само собой, такое возможно только для определенного класса хэш-функций)]]> Ivan_Govnoff Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89558 Sat, 11 Oct 2003 21:34:11 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89558 В исходной строке. Так сначала потребуется найти её.]]> zx1024 Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89557 Sat, 11 Oct 2003 20:50:38 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89557 идея - обычно ты ищещь первую букву искомой строки в тексте, потом проверяешь
совпадают ли остальные буквы. Дык а попробуй искать не первую букву искомой строки
а самую редкую. тогда колиество лишних сравнений (если 1 буквы совпала а остальные нет)
будет меньше.]]> Demo_S (unlogged) Алгоритмы https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89556 Sat, 11 Oct 2003 16:52:48 +0000 Алгоритм поиска подстроки в строке https://forum.sources.ru/index.php?showtopic=9114&view=findpost&p=89556 ХакМак Алгоритмы