Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1550. Чтение вслух
Бинарный поискХэш-функции
Олимпиадные задачи на русском языке
| 19/03/2011 | Южно-Уральский открытый командный чемпионат по программированию (C) |
| 19/05/2012 | Занятие 19 (E) |
| 05/05/2015 | Занятие 24 (B) |
| 07/05/2024 | Строки 2 (проводит BOGAT) (F) |
| 14/05/2025 | ЦОП1: полиномиальный хеш (проводит BOGAT) (F) |
Ограничения: время – 1000ms/2000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
