Есть длинная (до 10^5 символов) строка W в которой мы ищем кусочки текста. Каждый запрос представляет собой строчку Si длиной Li (10-20 символов) и нас интересует наибольший префикс этой строки содержащийся в W. После выполнения каждого запроса строчка Si конкатенируется в конец W а из начала W отбрасывается такое же число символов Li (так что размер W остаётся постоянным). Наверное без ущерба можно считать что добавляются просто случайные символы, не обязательно сама Si.
Количество запросов на порядок (порядки) больше размера W.
А есть ли какая-нибудь "классическая/популярная" структура позволяющая эффективно осуществлять такой поиск? В рамках реализации LZ77 из которого эта задача украдена она наверняка решалась различными способами (на ум лезут сразу сложно-придуманные деревья и хэш-таблицы с возможностью выкусывания "отслуживших" частей — но именно что как-то сложно). Но есть ли что-то такое что must know (а я дурак не знаю)?
Может я что-то не так понял, но разве нельзя просто в боре хранить все подстроки длины до 20?
Запрос — тупо обход бора. Конкатенация — тоже понятно.
Только, видимо, в вершине бора надо int хранить, чтобы нормально обрабатывать удаления.
Ну да, число таких подстрок
а как выбрасывать утратившие актуальность? Или теперь я чего-то недопонимаю?
будем хранить в каждой ноде количество таких подстрок. когда удаляем, вычитаем 1
Хм, похоже... подумаю, спасибо :)
Не, туплю таки. (это к вопросу в предыдущей правке которую смотреть не надо)
Можно, кстати, почитать исходники zlib, а именно — файл
deflate.c.Кому что не нравится? Исходник весит всего 70КБ и занимает меньше двух тысяч строчек. В самом первом комментарии описана идея, используемая для поиска подстроки в скользящем окне.
Понятно, что решение там эвристическое, т.к. абсолютно оптимальный с точки зрения степени сжатия алгоритм с использованием суффиксного массива и set-а будет работать еще медленнее, чем преобразование Барроуза-Уиллера в bzip2.
Я не минусовал :)
От себя скажу что действительно этот исходник один из немногих дающих материал по теме. Притом вербального описания используемого алгоритмом DEFLATE поиска вот так с полпинка с гугла я не нашёл когда-то — да и сейчас не вижу.
И действительно несмотря на довольно большой объём этот исходник содержит очень много достаточно читабельных комментов.
Единственный нюанс что тамошняя реализация это именно конкретная реализация, не какой-то "must know". Я-то просто материалы поясняющие для нескольких новичковых текстов про сжатие данных подыскиваю...
Чуть-чуть про "must know": мне обоснованно кажется, что на эту задачу одновременно простого, оптимального и быстрого решения не существует. Докажу от противного: если бы оно существовало, его бы использовали во всех программах, работающих с алгоритмом DEFLATE.
А Вашим новичкам, по-моему, хватит и реализации с поиском за линейное время (которую они сами же и напишут). Кто заинтересованы – те сами додумаются, что в реальных библиотеках используются более оптимальные алгоритмы и что многие из этих библиотек – опенсорсные.
А еще я придумал, как решить задачу за время
с потребляемой памятью 
. Решение нетривиальное, но без извращений. Если есть те, кому это интересно – могу рассказать.
UPD. Я нашел в своем решении недочет, множитель
пока можно заменить на 
.
UPD2. Недочет устранен, но я нашел в сети статьи про линейные алгоритмы. Ну что же, спасибо за упражнение для мозгов :).
Александр, спасибо за подробный ответ :)
Мне кажется что с этой задачей ситуация такая: "скользящее окно" является фичей обосновать нужность которой затруднительно, поэтому появившиеся модификации алгоритма работающие с "нескользящим" окном или "словарём" могут быть и проще и эффективнее — например
LZW, которое мы кажется где-то между школой и институтом писали в качестве упражнения на деревья...Если у вас найдётся лишняя минутка для этого то я б с удовольствием вас почитал (м.б. только это из комментов в пост вынести, если букв много)!