Алгоритм и структура для поиска большого количества строк в другом массиве строк

Здравствуйте!

Я решаю следующую задачу:
Есть файл со "строками" (средняя длина которых 40-50 символов) и таких строк порядка 100000. Есть другой файл, в котором в каждой строке написаны "слова"(средняя длина 8-15 символов). Требуется для каждой "строки" из первого файла вывести все "слова"(из второго файла), которые содержатся в "строке".

Я пробую подобрать наиболее быстрый алгоритм для работы. Есть время на препроцессинг и в принципе - нет ограничений на использование памяти.

Поскольку искать надо ВСЕ во ВСЕМ, то выходит, что общая сложность - O(m*n), где m - количество "строк" в файле, n - количество "слов" во втором файле.
Это вроде бы никак оптимизировать не выйдет. (или есть варинты?)

Так что я основной упор делаю именно в поиске подстроки в строке. (еще раз замечу, что их длины довольно маленькие - 50 - строка, 15 - подстрока)

http://algolist.manual.ru/search/esearch/index.php - тут есть сравнительние сложности алгоритмов на строках.

Сейчас я вижу следующие пути решения, посоветуйте, пожалуйста, что больше подойдет или посоветуйте, что-нибудь другое:
1) Писать алгоритм Кнута-Морриса-Пратта, который даст сложность - сумма обоих строк, то бишь около 65 операций на одну пару.
2) Объединить строки из первого файла с каким-нибудь разделителем (например #) и пробовать искать слова тем же самым КМП.
3) Построить бор(суффиксное дерево) для строки из варианта 2 и искать слова по нему... Про бор я читала, понимаю как он строится, но вот не могу понять - могу ли я в него много строк поместить? (это ведь просто добавит в него новые тернимальные состояния, так ведь?)

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

Заранее спасибо всем откликнувшимся!

Если не ошибаюсь, префикс-функцию и z-функцию можно как-то использовать. Одна из них позволяет проверять на вхождение нескольких подстрок - по-моему, z-функция.

0

Сообщение от hilda92 Здравствуйте! Есть файл со "строками" (средняя длина которых 40-50 символов) и таких строк порядка 100000. Есть другой файл, в котором в каждой строке написаны "слова"(средняя длина 8-15 символов). Требуется для каждой "строки" из первого файла вывести все "слова"(из второго файла), которые содержатся в "строке".

Пример: ищем слово "abs". Если во втором файле есть слово "myabs" - оно должно быть выведено? Если нет (считается только слово целиком) - то все очень просто, любой ассоциативный контейнер. Иначе конечно хужее

0