Есть длинная (до 10^5 символов) строка W в которой мы ищем кусочки текста. Каждый запрос представляет собой строчку Si длиной Li (10-20 символов) и нас интересует наибольший префикс этой строки содержащийся в W. После выполнения каждого запроса строчка Si конкатенируется в конец W а из начала W отбрасывается такое же число символов Li (так что размер W остаётся постоянным). Наверное без ущерба можно считать что добавляются просто случайные символы, не обязательно сама Si.

Количество запросов на порядок (порядки) больше размера W.

А есть ли какая-нибудь "классическая/популярная" структура позволяющая эффективно осуществлять такой поиск? В рамках реализации LZ77 из которого эта задача украдена она наверняка решалась различными способами (на ум лезут сразу сложно-придуманные деревья и хэш-таблицы с возможностью выкусывания "отслуживших" частей — но именно что как-то сложно). Но есть ли что-то такое что must know (а я дурак не знаю)?