#P9344. 卡牌⼤师的归属

    ID: 5732 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-后缀自动机endpos 等价类小并大合并集合有序集合离线查询树状数组计数排序

卡牌⼤师的归属

题目描述

给定一个长度为 nn 的命运之串 SS。它的每个非空前缀都代表一个结局。长度分别为 a,ba,b 的两个结局的关联值,是前缀 S[1…a]S[1\ldots a] 与 S[1…b]S[1\ldots b] 的最长公共后缀长度。

每次询问给出 l,rl,r。可以选择的结局是所有长度位于 [l,r][l,r] 的前缀。求两个不同结局的最大关联值。如果区间里只有一个结局,输出 00。

输入格式

第一行两个整数 n,mn,m,分别表示字符串长度和询问数。

第二行是长度为 nn 的字符串 SS。随后 mm 行,每行两个整数 l,rl,r,满足 1≤l≤r≤n1\le l\le r\le n。

若 n=m=0n=m=0,没有字符串或询问需要处理。

输出格式

输出 mm 行,每行一个整数,表示对应询问的答案。

样例

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

原赛其余样例

数据范围

0≤n,m≤1050\le n,m\le10^5。现有原生数据的非空字符串均由小写英文字母组成。

原赛子任务 nn 上限 mm 上限 原赛分值
1 00 1
2 1010 4
3 400400 10
4 30003000
5 10510^5 500500 15
6 3000030000 25
7 10510^5 35

原 PDF 题面