← 返回题目列表

Codeforces · 2164/H

H. 回文回文

中文机器翻译题面 查看原题

我们定义 幽默值 字符串 $$$t$$$ 的 作为其中至少出现两次的最长回文字符串的长度。

形式上,字符串 $$$p$$$ 是 关于$$$t$$$的幽默,当且仅当满足以下两个条件时:

  1. $$$p$$$ 是回文,并且
  2. 存在 至少两个不同的 索引 $$$i \in [1, |t| - |p| + 1]$$$,使得 $$$t[i, i + |p| - 1] = p$$$。 $$$t$$$ 的

的 幽默值 字符串 $$$t$$$ 的 被定义为所有长度中的最大长度 幽默 字符串 关于 $$$t$$$.

给您一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中仅包含小写拉丁字母和 $$$q$$$ 查询。每个查询包含两个整数$$$l_i$$$、$$$r_i$$$,需要找到字符串$$$s[l_i, r_i]$$$的幽默值。

这里,$$$a[l, r]$$$ 被定义为字符串 $$$a_l,a_{l+1},\ldots,a_r$$$。

输入

第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1\le n,q\le 5\cdot10^5$$$)。

第二行包含字符串 $$$s$$$。

接下来的 $$$q$$$ 行包含查询的描述。第 $$$i$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$)。

输出

在第 $$$i$$$ 行上,输出第 $$$i$$$ 查询的答案。

示例

输入
复制

12 6
aaaabbbbaaaa
1 12
2 7
3 10
4 7
5 9
4 5

输出
复制

4
2
3
2
3
0

注意

在第一个查询中,以下回文字符串至少出现两次: a、aa、aaa、aaaa、b、bb、bbb。最长的是 啊啊啊,所以 幽默值 字符串 $$$t$$$ 的 是 $$$4$$$。

在第二个查询中,最长的查询之一 幽默 相对于 $$$s[2, 7]$$$ 的字符串是 aa.