Skip to content

1016: 水体

题目

题目描述

给定一个长度为$𝑛$的字符串$𝑆$,给出$𝑞$个询问,每次询问子串$𝑆[𝑙. . 𝑟]$的最长回文子串长度。字符串下标从$0$开始。

输入格式

第一行,一个整数$𝑛$。

第二行,一个长度为$𝑛$的字符串$𝑆$。

第三行,一个整数$𝑞$,代表询问个数。

输出格式

$𝑞$行,每行一个整数表示答案。

样例输入

Input 1

6 kqppqk 3 2 3 1 4 0 5

Input 2

10 tokotoriro 4 1 3 0 9 0 5 0 0

Input 3

8 myymmyym 3 0 2 1 3 1 6

样例输出

Output 1

2 4 6

Output 2

3 5 5 1

Output 3

2 2 6

数据范围

对于$20\%$的数据,满足$1 \le 𝑛, 𝑞 \le 2 \times 10^2$

对于$30\%$的数据,满足$1 \le 𝑛, 𝑞 \le 2 \times 10^3$

对于$100\%$的数据,满足$1 \le 𝑛, 𝑞 \le 1 \times 10^5,0 \le 𝑙 \le 𝑟 < 𝑛$,$𝑆$只包含小写拉丁 字母。

其中最后一档部分分有一个数据点只存在前两个小写字母,有一个数据点只存在前五个小写字母。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!