Codeforces Round 943 (Div. 3) |
---|
Закончено |
Это простая версия задачи. В этой версии $$$l=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$$$. В этой версии $$$l=r$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого теста содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le l = r \le n \le 2 \cdot 10^5$$$) — длина строки и заданный диапазон.
Вторая строка каждого набора содержит строку $$$s$$$ из $$$n$$$ символов, все символы — строчные буквы английского алфавита.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите $$$r-l+1$$$ значений: $$$f_l,\dots,f_r$$$.
73 3 3aba3 3 3aaa7 2 2abacaba9 4 4abababcab10 1 1codeforces9 3 3abafababa5 3 3zpozp
0 1 3 2 10 2 0
В первом примере $$$n=k$$$, поэтому единственное деление $$$aba$$$ — $$$\color{red}a\color{blue}b\color{orange}a$$$. Ответ — ноль, потому что у этих строк нет общего префикса.
Во втором примере единственное деление — $$$\color{red}a\color{blue}a\color{orange}a$$$. Их самый длинный общий префикс равен одному.
Название |
---|