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

printЗадачи

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

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

3
1
0
2
loading