bzoj#P3230. 相似子串

相似子串

题目描述

对于一个 长度为 nn 的字符串 ss,将 ss本质不同的所有字串按字典序从小到大 排序。

比如串 ababa,共有 99 个本质不同的字串,按要求排序后得到:

顺序 子串 顺序 子串
1 a 6 b
2 ab 7 ba
3 aba 8 bab
4 abab 9 baba
5 ababa

我们定义两个子串 s[l...r]s[l...r]s[p...q]s[p...q] 的相似程度为 f=a2+b2f = a^2 + b^2 的最大值,其中 a,ba,b 满足:

  • s[l...l+a1]=s[p...p+a1]s[l...l+a-1] = s[p...p+a-1]s[rb+1...r]=s[qb+1...q]s[r-b+1...r] = s[q-b+1...q]0arl+10 \leq a \leq r - l + 10bqp+10 \leq b \leq q - p + 1

接下来,我们要询问的是,排序后的第 ii 个子串和第 jj 个子串的相似程度是多少。

输入格式

输入第 11 行,包含 33 个整数 n,Qn,QQQ 代表询问组数。

22 行是字符串 ss

接下来 QQ 行,每行两个整数 iijj1ij1 \leq i \leq j)。

输出格式

输出共 QQ 行,每行一个数表示每组询问的答案。如果不存在第 ii 个子串或第 jj 个子串,则输出 1-1

5 3
ababa
3 5
5 9
8 10
18
16
-1

样例说明

  • 第1组询问:两个子串是 aba,ababaf=32+32=18f = 3^2 + 3^2 = 18
  • 第2组询问:两个子串是 ababa,babaf=02+42=16f = 0^2 + 4^2 = 16
  • 第3组询问:不存在第 1010 个子串,输出 1-1

数据规模与约定

  • 对于 100%100\% 的数据,0n1050 \leq n \leq 10^50Q1050 \leq Q \leq 10^5,字符串只由小写字母 a ~ z 组成。

题目来源

后缀数组+二分+RMQ