Быстрый поиск строки в списке строк с предварительным хешированием

@FutureCome · Регистрация: 19.12.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте.
Необходимо реализовать быстрый поиск строки в списке строк с предварительным хешированием в целях исследования (изучения).
Реализовываться будет на Java, если это имеет значение.
Теперь подробнее.
Входные данные

Список (массив, List) строк, назовём его lstStrings;
Список дополнительных данных, ассоциированных со строками, предназначенных для сортировки результата (например, дата последнего изменения строки);
Строка, которую нужно искать в исходном списке строк srcStrings, назовём её ptrnString;
Число limitNumber, ограничивающее максимальное количество строк, которые могут быть возвращены в качестве результата выполнения алгоритма (т.е. в результате не более limitNumber найденных строк).

Задача алгоритма
Поиск всех строк в списке lstStrings, которые начинаются со строки ptrnString, за максимально короткое время.
Подробности реализации
Реализовать придётся, скорее всего, как-то через хеширование или индексацию для достижения максимальной скорости при сотнях тысяч исходных строк и запросов.
Например, первый метод индексирует весь список исходных строк, подготавливает необходимые структуры для дальнейшего поиска. А второй метод уже непосредственно осуществляет поиск.
Найти нужно не более limitNumber строк.
Результирующий список необходимо отсортировать по определённым правилам: с каждой строкой ассоциирована дата её изменения. Сортировку результатов необходимо провести по дате изменения. Если даты изменения совпадают - в лексикографическом (алфавитном) порядке.
Выходные данные

Список (массив) строк, которые начинаются с искомой строки ptrnString, в нужной последовательности.

В какую сторону мне начать искать...? Какие быстрые алгоритмы существуют для решения этой задачи? Подскажите, как лучше решить эту задачу?
Заранее спасибо.

@salam · 13.04.2013, 10:29

с помощью хэшей вы можете отвечать на каждый запрос за O(1). таким образом итоговая сложность O(n*l + q). оставлю так, ибо мне неизвестны соотношения между количеством запросов и длинами строк.
в общем понятно уже, что тонкий момент в этой задаче - подсчет хэшей. прежде всего нужно понять, что хэши нужно считать только для префикса длины искомой строки. то есть если мы ищем "abcd" в строке "abcdefgrjf", то смысл есть знать только хэш первых четырех символов строки "abcdefgrjf". если вы грамотно посчитаете хэши, то дальше давать ответ будет сплошным удовольствием.
если будут вопросы, пишите, не стесняйтесь)

Добавлено через 9 минут
извините, не то сказал... с помощью хэшей вы можете отвечать на каждый запрос за O(n). таким образом итоговая сложность O(n*l + n*q). оставлю так, ибо мне неизвестны соотношения между количеством запросов и длинами строк.

10.01.2014, 02:03

Здравствуйте! Сейчас решаю подобную задачу. Длина искомой строки известна только после индексации данных. Получается в любом случае нужно считать хэши всех префиксов и потом уже брать нужной длины. Если так делать, то подозреваю, что не получится уложиться в ограничение по памяти в 64 Мб (по ТЗ). А если сохранять в файлы, то это дополнительно время. Буду очень признателен, если подбросите идей или датите комментарии. Спасибо.

@salam · 10.01.2014, 08:59

если вас устраивает отвечать на каждый запрос за O(L), где L - длина искомой строки, то можно строить бор. тогда длина префикса абсолютно не принципиальна.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@FutureCome 107 / 107 / 9 Регистрация: 19.12.2010 Сообщений: 417

	Быстрый поиск строки в списке строк с предварительным хешированием 26.01.2013, 21:36. Показов 2408. Ответов 3 Метки нет (Все метки) Здравствуйте. Необходимо реализовать быстрый поиск строки в списке строк с предварительным хешированием в целях исследования (изучения). Реализовываться будет на Java, если это имеет значение. Теперь подробнее. Входные данные Список (массив, List) строк, назовём его lstStrings; Список дополнительных данных, ассоциированных со строками, предназначенных для сортировки результата (например, дата последнего изменения строки); Строка, которую нужно искать в исходном списке строк srcStrings, назовём её ptrnString; Число limitNumber, ограничивающее максимальное количество строк, которые могут быть возвращены в качестве результата выполнения алгоритма (т.е. в результате не более limitNumber найденных строк). Задача алгоритма Поиск всех строк в списке lstStrings, которые начинаются со строки ptrnString, за максимально короткое время. Подробности реализации Реализовать придётся, скорее всего, как-то через хеширование или индексацию для достижения максимальной скорости при сотнях тысяч исходных строк и запросов. Например, первый метод индексирует весь список исходных строк, подготавливает необходимые структуры для дальнейшего поиска. А второй метод уже непосредственно осуществляет поиск. Найти нужно не более limitNumber строк. Результирующий список необходимо отсортировать по определённым правилам: с каждой строкой ассоциирована дата её изменения. Сортировку результатов необходимо провести по дате изменения. Если даты изменения совпадают - в лексикографическом (алфавитном) порядке. Выходные данные Список (массив) строк, которые начинаются с искомой строки ptrnString, в нужной последовательности. В какую сторону мне начать искать...? Какие быстрые алгоритмы существуют для решения этой задачи? Подскажите, как лучше решить эту задачу? Заранее спасибо. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	13.04.2013, 10:29
	с помощью хэшей вы можете отвечать на каждый запрос за O(1). таким образом итоговая сложность O(nl + q). оставлю так, ибо мне неизвестны соотношения между количеством запросов и длинами строк. в общем понятно уже, что тонкий момент в этой задаче - подсчет хэшей. прежде всего нужно понять, что хэши нужно считать только для префикса длины искомой строки. то есть если мы ищем "abcd" в строке "abcdefgrjf", то смысл есть знать только хэш первых четырех символов строки "abcdefgrjf". если вы грамотно посчитаете хэши, то дальше давать ответ будет сплошным удовольствием. если будут вопросы, пишите, не стесняйтесь) Добавлено через 9 минут* извините, не то сказал... с помощью хэшей вы можете отвечать на каждый запрос за O(n). таким образом итоговая сложность O(nl + nq). оставлю так, ибо мне неизвестны соотношения между количеством запросов и длинами строк. 0

Ks4ndr
	10.01.2014, 02:03
	Здравствуйте! Сейчас решаю подобную задачу. Длина искомой строки известна только после индексации данных. Получается в любом случае нужно считать хэши всех префиксов и потом уже брать нужной длины. Если так делать, то подозреваю, что не получится уложиться в ограничение по памяти в 64 Мб (по ТЗ). А если сохранять в файлы, то это дополнительно время. Буду очень признателен, если подбросите идей или датите комментарии. Спасибо.

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	10.01.2014, 08:59
	если вас устраивает отвечать на каждый запрос за O(L), где L - длина искомой строки, то можно строить бор. тогда длина префикса абсолютно не принципиальна. 0