A16756 | $PalindromePalindrome$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

我们定义字符串 $t$ 的幽默值为：在 $t$ 中至少出现两次的最长回文子串的长度。 具体地，对于一个字符串 $t$，只有当以下两个条件同时满足时，字符串 $p$ 才称为 $t$ 的幽默字符串： 1. $p$ 是回文串； 2. 存在至少两个不同的下标 $i \in [1, |t| - |p| + 1]$，使得 $t[i, i + |p| - 1] = p$。 字符串 $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\times10^5$）。 第二行包含一个字符串 $s$。 接下来的 $q$ 行，每行包含两个整数 $l_i$、$r_i$（$1\le l_i\le r_i\le n$），表示一次询问。

对于第 $i$ 个询问，输出一行答案。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出