Здравствуйте!
У меня стоит следующая задача:
Есть файл со "строками" (средняя длина которых 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, если знаете полезные библиотеке по теме - также буду признательна.
Заранее спасибо!
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.