#P9344. 卡牌⼤师的归属
卡牌⼤师的归属
题目描述
给定一个长度为 的命运之串 。它的每个非空前缀都代表一个结局。长度分别为 的两个结局的关联值,是前缀 与 的最长公共后缀长度。
每次询问给出 。可以选择的结局是所有长度位于 的前缀。求两个不同结局的最大关联值。如果区间里只有一个结局,输出 。
输入格式
第一行两个整数 ,分别表示字符串长度和询问数。
第二行是长度为 的字符串 。随后 行,每行两个整数 ,满足 。
若 ,没有字符串或询问需要处理。
输出格式
输出 行,每行一个整数,表示对应询问的答案。
样例
10 10
adawefrawe
1 5
2 4
3 6
4 7
5 8
6 9
7 10
1 10
1 10
2 3
1
0
0
0
0
0
0
3
3
0
数据范围
。现有原生数据的非空字符串均由小写英文字母组成。
| 原赛子任务 | 上限 | 上限 | 原赛分值 |
|---|---|---|---|
| 1 | 1 | ||
| 2 | 4 | ||
| 3 | 10 | ||
| 4 | |||
| 5 | 15 | ||
| 6 | 25 | ||
| 7 | 35 | ||