CF1968G2.Division + LCP (hard version)

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是该问题的困难版本。在本版本中 $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$ ）——字符串的长度和给定的区间。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$ ，所有字符均为小写英文字母。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出 $r-l+1$ 个值： $f_l, f_{l+1}, \dots, f_r$ 。

输入输出样例

输入#1

7
3 1 3
aba
3 2 3
aaa
7 1 5
abacaba
9 1 6
abababcab
10 1 10
aaaaaaawac
9 1 9
abafababa
7 2 7
vvzvvvv

输出#1

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

说明/提示

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页