Назовите самые  быстрые алгоритмы поиска подтекста в большом объеме текста. Например : дано 12 000 000 писем , нужно чтобы максимум за 0.5 сек 60 юзеров могли получить результат поиска ?????????????????????

Алгоритмов на самом деле огромное количество, поэтому стоит просто поискать...

Но интерес лично у меня вызвало дерево ван Эмде Боаса. 

Скорее всего вам такое не подойдет, но тем не менее ...

Дерево ван Эмде Боаса - это ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2k, или, числа, состоящие не более чем из k бит. Главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов. Список поддерживающихся операций: insert, remove, getmin, getmax, find, findnext, findprevious.

Естественно, раз такая скорость, в жертву приносится память... 

Кстати, с числами легко можно связать любую информацию, хоть и текстовую.

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



Это сообщение отредактировал(а) gahcep - 15.8.2011, 07:35

Зачем смотреть Кнута?

Зачем читать Кнута? Хм... даже затрудняюсь ответить... Может быть потому, что там есть почти все ответы на то, какие алгоритмы есть, как они используются и приведены примеры. А если посмотреть содержимое томов с номерком более чем 3, то еще можно подчерпнуть что-нибудь интересное. 

Алгоритм поиска подтекста в тексте = алгоритм поиска подстроки в строке, не, а?

Добавлено через 3 минуты и 48 секунд
dimon444, у вас в вопросе две проблемы. 

Первая - это алгоритм поиска строки в подстроке - одна задача, давно решенная. 

Вторая - в скорости работы с жестким диском (или что у вас там используется), а точнее в оптимизации чтения с него, ибо 12 000 000 писем перед тем, как обработать еще открыть надо...

Кстати, с числами легко можно связать любую информацию, хоть и текстовую
"

Конечно, текст размером в х, кодируется числом размером тетта(х) ваш алгоритм, обеспечит поиск за время 
тета(лог лог( 10 в степени х) что посути лог(х) и не надо никакого асоциатавного поиска.


-----------
Кнут здесь не подойдет, он достаточно давно и тяжело написан. Есть современные и более понятные учебники.

Дядька до сих пор пишет, и исправляет уже изданные тома.
5-й том он планирует закончить только к 2015 году.
На домашней страничке у него, есть исправления ошибок и дополнительные главы для первых 3-ех томов, не вошедшие в издание.