#P3230. 相似子串

    ID: 2407 传统题 1000ms 512MiB 尝试: 2152 已通过: 369 难度: 7 上传者: 标签>难度分类提高字符串后缀数组排序与序列处理倍增计数排序Kasai 算法LCP+RMQ数据结构ST 表一维前缀和二分查找CF2200

相似子串

相似子串

题目描述

对于一个 长度为 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+a−1]=s[p...p+a−1]s[l...l+a-1] = s[p...p+a-1],s[r−b+1...r]=s[q−b+1...q]s[r-b+1...r] = s[q-b+1...q],0≤a≤min⁡(r−l+1,q−p+1)0 \leq a \leq \min(r-l+1,q-p+1),0≤b≤min⁡(r−l+1,q−p+1)0 \leq b \leq \min(r-l+1,q-p+1)。

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

输入格式

第一行包含两个整数 n,Qn,Q,分别表示字符串长度和询问数。

第 22 行是字符串 ss。

接下来 QQ 行,每行两个整数 ii 和 jj(1≤i≤j1 \leq i \leq j)。

输出格式

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

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

样例说明

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

数据规模与约定

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