相似子串
题目描述
对于一个 长度为 n 的字符串 s,将 s 的 内容互异的所有连续子串按字典序从小到大 排序。
比如串 ababa,共有 9 个本质不同的字串,按要求排序后得到:
| 顺序 |
子串 |
顺序 |
子串 |
| 1 |
a |
6 |
b |
| 2 |
ab |
7 |
ba |
| 3 |
aba |
8 |
bab |
| 4 |
abab |
9 |
baba |
| 5 |
ababa |
|
我们定义两个子串 s[l...r] 和 s[p...q] 的相似程度为 f=a2+b2 的最大值,其中 a,b 满足:
- s[l...l+a−1]=s[p...p+a−1],s[r−b+1...r]=s[q−b+1...q],0≤a≤min(r−l+1,q−p+1),0≤b≤min(r−l+1,q−p+1)。
接下来,我们要询问的是,排序后的第 i 个子串和第 j 个子串的相似程度是多少。
输入格式
第一行包含两个整数 n,Q,分别表示字符串长度和询问数。
第 2 行是字符串 s。
接下来 Q 行,每行两个整数 i 和 j(1≤i≤j)。
输出格式
输出共 Q 行,每行一个数表示每组询问的答案。如果不存在第 i 个子串或第 j 个子串,则输出 −1。
5 3
ababa
3 5
5 9
8 10
18
16
-1
样例说明
- 第1组询问:两个子串是
aba,ababa。f=32+32=18。
- 第2组询问:两个子串是
ababa,baba。f=02+42=16。
- 第3组询问:不存在第 10 个子串,输出 −1。
数据规模与约定
- 对于 100% 的数据,0≤n≤105,0≤Q≤105,字符串只由小写字母
a ~ z 组成。