07/04/2025 03:51:21

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1550. Чтение вслух

Ограничения: время – 1000ms/2000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Паниковский и Балабанов вместе читают вслух "дело Корейко". Но первый читает дело с

$i$ -го символа, а второй – с

$j$ -го символа. Чтение продолжается, пока читаемые буквы совпадают. Сколько букв они смогут прочитать, прежде чем обнаружат, что читают дело, начиная с разных позиций.

В первой строке ввода дана строка

$S$ из строчных латинских букв длиной от 1 до 100000 символов. В следующей строке дано одно целое число

$Q$ – количество запросов (

$1\ ≤\ Q\ ≤\ 100000$ ). В следующих

$Q$ строках даны запросы. Каждый запрос задаётся парой целых чисел

$(i,j)$ (

$1\ ≤\ i,\ j\ ≤\ |S|$ ) – индексы символов, с которых надо начинать читать.

Выведите

$Q$ строк, в каждой из которых должно быть одно целое число – количество символов, совпадающих при чтении подстрок, начинающихся с

$i$ -го и

$j$ -го символа (т.е. длина максимального общего префикса этих двух подстрок).

Пример ввода

abacaba
4
1 5
3 5
4 2
2 6

Пример вывода

19/03/2011	Южно-Уральский открытый командный чемпионат по программированию (C)
19/05/2012	Занятие 19 (E)
05/05/2015	Занятие 24 (B)
04/04/2023	Строки 2 (проводит BOGAT) (F)
07/05/2024	Строки 2 (проводит BOGAT) (F)