bzoj#P3230. 相似子串
相似子串
题目描述
对于一个 长度为 的字符串 ,将 的 本质不同的所有字串按字典序从小到大 排序。
比如串 ababa
,共有 个本质不同的字串,按要求排序后得到:
顺序 | 子串 | 顺序 | 子串 |
---|---|---|---|
1 | a |
6 | b |
2 | ab |
7 | ba |
3 | aba |
8 | bab |
4 | abab |
9 | baba |
5 | ababa |
我们定义两个子串 和 的相似程度为 的最大值,其中 满足:
- ,,,。
接下来,我们要询问的是,排序后的第 个子串和第 个子串的相似程度是多少。
输入格式
输入第 行,包含 个整数 。 代表询问组数。
第 行是字符串 。
接下来 行,每行两个整数 和 ()。
输出格式
输出共 行,每行一个数表示每组询问的答案。如果不存在第 个子串或第 个子串,则输出 。
5 3
ababa
3 5
5 9
8 10
18
16
-1
样例说明
- 第1组询问:两个子串是
aba
,ababa
。。 - 第2组询问:两个子串是
ababa
,baba
。。 - 第3组询问:不存在第 个子串,输出 。
数据规模与约定
- 对于 的数据,,,字符串只由小写字母
a
~z
组成。
题目来源
后缀数组+二分+RMQ