Codeforces Round 943 (Div. 3) |
---|
Закончено |
Это cложная версия задачи. В этой версии $$$l\le r$$$.
Дана строка $$$s$$$. Для фиксированного $$$k$$$ рассмотрим деление $$$s$$$ на ровно $$$k$$$ непрерывных подстрок $$$w_1,\dots,w_k$$$. Пусть $$$f_k$$$ — максимально возможное $$$LCP(w_1,\dots,w_k)$$$ среди всех делений.
$$$LCP(w_1,\dots,w_m)$$$ — это длина самого длинного общего префикса строк $$$w_1,\dots,w_m$$$.
Например, если $$$s=abababcab$$$ и $$$k=4$$$, то возможное деление $$$\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$$$. $$$LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$$$ равно $$$2$$$, так как $$$ab$$$ — самый длинный общий префикс этих четырех строк. Обратите внимание, что каждая подстрока состоит из непрерывного сегмента символов, и каждый символ принадлежит ровно одной подстроке.
Ваша задача — найти $$$f_l,f_{l+1},\dots,f_r$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого теста содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n \le 2 \cdot 10^5$$$) — длина строки и заданный диапазон.
Вторая строка каждого набора содержит строку $$$s$$$ из $$$n$$$ символов, все символы — строчные буквы английского алфавита.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите $$$r-l+1$$$ значений: $$$f_l,\dots,f_r$$$.
73 1 3aba3 2 3aaa7 1 5abacaba9 1 6abababcab10 1 10aaaaaaawac9 1 9abafababa7 2 7vvzvvvv
3 1 0 1 1 7 3 1 1 0 9 2 2 2 0 0 10 3 2 1 1 1 1 1 0 0 9 3 2 1 1 0 0 0 0 2 2 1 1 1 0
Название |
---|