Ответ 1
В зависимости от того, сколько раз вы хотите выполнить поиск, вы хотите использовать поисковую систему или нет. Если вы хотите много раз искать, используйте поисковую систему, иначе: нет. Я расскажу, как реализовать оба сценария здесь.
При использовании поисковой системы: похоже, что вы ищете подстроки, а это значит, что вы должны индексировать свои файлы как таковые, используя свою любимую поисковую систему, предпочтительно такую, которую вы можете настроить (lucene, terrier и т.д.). Техника, в которой вы нуждаетесь, - это индексирование триграмм, то есть: все 3-значные комбинации должны быть проиндексированы. F.ex.: "foobar" будет генерировать "foo", "oob", "oba" и "bar". При поиске вы хотите сделать то же самое с вашим запросом и выдать запрос поисковой системы с И всех этих триграмм. (Это запустит объединение слияния в списках проводки из документов, которое вернет их идентификатор или все, что вы разместите в списках проводки).
В качестве альтернативы вы можете реализовать массивы суффиксов и индексировать свои файлы один раз. Это даст немного большую гибкость, если вы захотите найти короткие (1-2 char) подстроки, но с точки зрения индексов сложнее поддерживать. (Есть несколько исследований в CWI/Amsterdam для быстрого индексирования суффикса)
Если вы хотите искать только несколько раз, алгоритм для использования - либо Бойер-Мур (я обычно использую Бойер-Мур-воскресенье, как описано в [Graham A. Stephen, String Search]) или скомпилированный DFA (вы может построить их из NFA, что легче сделать). Тем не менее, это только даст вам небольшое увеличение скорости по той простой причине, что диск IO, вероятно, является вашим узким местом и сравнивает кучу байтов, которые нужно декодировать в любом случае, довольно быстро.
Самое большое улучшение, которое вы можете сделать, это не чтение вашего файла по строкам, а в блоках. Вы должны настроить NTFS на использование размера блока в 64 КБ, если сможете, и читать файлы в размножении 64 КБ - считайте 4 МБ или более в одном чтении. Я бы даже предложил использовать асинхронный ввод-вывод, чтобы вы могли одновременно читать и обрабатывать (ранее прочитанные данные). Если вы сделаете это правильно, это уже должно дать вам двухсекундную реализацию на 10 МБ на большинстве современных аппаратных средств.
И последнее, но не менее важное: аккуратный трюк, используемый во время поиска информации, также позволяет сжать ваши данные с использованием алгоритма быстрого сжатия. Поскольку диск IO медленнее операций с памятью/процессором, это, вероятно, также поможет. Компилятор Google Snappy - хороший пример быстрого алгоритма сжатия.