Добрый день. Я был членом жюри на Кировской олимпиаде, она проходила на этих же задачах. У себя на разборе мы еще рассказывали такое решение.

Выкинем все запросы, длина которых не укладывается в ограничение (левая позиция, правая позиция). Сгруппируем запросы по длинам и будем рассматривать сразу группу. Скидаем (хэш, левая позиция, правая позиция) всех строк-запросов рассматриваемой длины в хэш-таблицу. Причем складывать их туда будем таким образом, чтобы среди запросов с равным хэшем вначале шел тот, у которого левый край меньше.

Мы знаем длину рассматриваемых запросов, будем брать хэш подстроки соответствующей длины из большой строки начиная с первой позиции. Возможны следующие варианты:

1. В таблице нет такого хэша. Ничего не происходит.

2. Запрос с соответствующим хэшем лежит в таблице, его левая позиция не больше, чем начало рассматриваемой подстроки в большой строке, по правой позиции запрос укладывается. Тогда пометим этот запрос знаком "+" и выкинем его из таблицы. Перейдем к рассмотрению следующего элемента таблицы.

3. Запрос есть, но его левая позиция больше. Понятно, что даже если в таблице и есть элементы с таким же хэшем, то их левая позиция будет еще больше (мы их складывали в таблицу в таком порядке). Значит дальше эту подстроку можно не рассматривать.

4. Запрос есть, левая граница не больше, но правая не укладывается. Тогда для этого запроса гарантированно будет "-", выкинем его из таблицы и перейдем к рассмотрению следующего элемента таблицы.

Сложность решения вроде бы O(|s|*sqrt(|t|)), где |s| - длина большой строки, |t| - суммарная длина запросов. Наше решение на тестах жюри работало примерно 0,7 секунды (Pentium 4 3GHz).