Алгоритм поиска подстроки в строке

Народ помогите найти алгоритм для поиска в строке подстроки, обічній дельфиевский Pos() слишком слабый и в больших оюъемах (30МБ) уже ужасно тормозит, может посоветуете чтонибудь другое ? И еще как снять ограничение на размер открываемого файла в дельфи?

Самому написать.
идея - обычно ты ищещь первую букву искомой строки в тексте, потом проверяешь
совпадают ли остальные буквы. Дык а попробуй искать не первую букву искомой строки
а самую редкую. тогда колиество лишних сравнений (если 1 буквы совпала а остальные нет)
будет меньше.

Редкую где?
В исходной строке. Так сначала потребуется найти её.

Есть такой алгоритм(кажется (с) Кнут):

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 - 11.10.03, 22:18

Что-то мне кажется, что етот, с хеш-функцией, алгоритм (1) будет НЕ быстрее, чем ранее предложенный алгоритм (2) (поиск первой буквы, затем сравнение остальных), в том случае, если  буквы в просматриваемом тексте распределены равномерно... Если же неравномерно, то (1) в среднем будет работать с такой же скоростью, что и (2), но у (2) будут случаи "плохих" и "хороших" искомых подстрок

Самым быстрым, вроде, считают алгоритм Бойера-Мура, но его еффективность проявляется только при значительной длине искомой подстроки.

Сообщение отредактировано: Visitor - 12.10.03, 16:45

У меня курсовик был на эту тему. Могу намылить.

Цитата Visitor, 12.10.03, 03:18:46

Что-то мне кажется, что етот, с хеш-функцией, алгоритм (1) будет НЕ быстрее, чем ранее предложенный алгоритм (2) (поиск первой буквы, затем сравнение остальных), в том случае, если  буквы в просматриваемом тексте распределены равномерно... Если же неравномерно, то (1) в среднем будет работать с такой же скоростью, что и (2), но у (2) будут случаи "плохих" и "хороших" искомых подстрок

Ясен пень, если тебе хватает первого метода, то и не нечего извращаться, просто я предлагаю другой хороший вариант.

редкая - например "Ъ".

хеш будет быстрее, так как больше неправильных вариантов будут отсекаться без посимвольного сравнения. тут кстати где то рядом уже была подобная тема.

кстати простой вариант с первой буквой - этот тот же хеш. просто хеш фукнция от строки - взять первую букву.

В журнале "Программист" была статья в свое время на эту тему.
Самый эффективный поиск там был начиная с конца текста.
Ищешь с конца первое вхождение первого символа подстроки. При повторяющихся символах в подстроке сдвигать можно на разнице между двумя вхождениями этих символов.
По-моему так....

Блин... Ну хоть строгое доказательство приводи Ни один алгоритм, не использующий знание о структуре искомой подстроки и просматриваемого текста, в среднем не будет работать быстрее, чем самый очевидный из уже предложенных

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

Сообщение отредактировано: Visitor - 13.10.03, 16:28

Цитата Visitor, 13.10.03, 20:22:23

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

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

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

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

Описан этот алгоритм и еще несколько 9включая на конечных автоматах) в журнале Программист #6 2002 "Алгоритмы: "умный" поиск в тексте"

Тогда сдаюсь - согласен