Общий префикс суффиксов

1000 мс · 256 МБ · всё или ничего

Дана строка $s$ и $q$ запросов вида $(i, j)$ : найдите длину наибольшего общего префикса суффиксов, начинающихся в позициях $i$ и $j$ .

В первой строке - строка $s$ из строчных латинских букв ( $1 \le |s| \le 10^5$ ).

Во второй строке - число запросов $q$ ( $0 \le q \le 10^5$ ).

В следующих $q$ строках - пары $i$ , $j$ ( $1 \le i, j \le |s|$ ).

Для каждого запроса выведите длину наибольшего общего префикса суффиксов.

ввод

ababa
3
1 3
1 2
5 5

вывод

3
0
1

ввод

ab
1
1 2

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.