1012. L. Yet Another Suffix Array Problem

题目描述

题目描述

给定一个长度为 (n) 的小写字母字符串 (S)，以及 (m) 次询问。

每次询问给出两个整数 (l,r)。令：

$$T=S_lS_{l+1}\cdots S_r,$$

并记 (q=r-l+1)。

考虑 (T) 的所有非空后缀。令 (SA_T[1],SA_T[2],\ldots,SA_T[q]) 表示这些后缀按字典序从小到大排列后的起点，其中起点按照 (T) 内从 (1) 开始的编号。如果一个字符串是另一个字符串的前缀，较短的字符串字典序更小。

定义 (T) 的 height 数组：

$$\operatorname{height}_T[1]=0,$$

对于每个 (2\le i\le q)：

$$height_T[i] = LCP[ T_{SA_T[i-1]}\cdots T_q,\, T_{SA_T[i]}\cdots T_q].$$

其中 (\operatorname{LCP}) 表示两个字符串的最长公共前缀长度。

令：

$$H=\max_{2\le i\le q}\operatorname{height}_T[i].$$

如果有多个下标 (i) 满足 (\operatorname{height}_T[i]=H)，取其中最小的 (i)。

对于每次询问，求 (H)，以及 (SA_T[i-1]) 和 (SA_T[i]) 对应的两个后缀在原字符串 (S) 中的起点。**两个起点的输出顺序必须与 (SA_T) 中的顺序相同。**每次询问保证 (H>0)。

样例解释

对于第一次询问，(T=\texttt{banana})。其后缀数组中的原串起点依次为：

$$6,4,2,1,5,3,$$

对应的 height 数组为：

$$0,1,3,0,0,2.$$

最大值为 (3)，最早在起点 (4) 和起点 (2) 对应的相邻后缀之间取得。

第二次询问中，(T=\texttt{banan})。后缀 an 是后缀 anan 的前缀，因此起点 (4) 排在起点 (2) 之前，答案为 2 4 2。

数据范围

• (1\le T\le 5)
• (2\le n\le 2\times 10^5)
• (1\le m\le 2\times 10^5)
• (1\le l<r\le n)
• (S) 仅包含小写英文字母
• 每次询问均保证 (H>0)
• 所有测试数据的 (n) 之和不超过 (4\times10^5)
• 所有测试数据的 (m) 之和不超过 (4\times10^5)

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)（(1\le T\le 5)），表示测试数据组数。

对于每组测试数据：

第一行包含两个整数 (n,m)（(2\le n\le 2\times 10^5)，(1\le m\le 2\times 10^5)）。

第二行包含一个长度为 (n) 的小写字母字符串 (S)。

接下来 (m) 行，每行包含两个整数 (l,r)（(1\le l<r\le n)），表示一次询问。

保证每个询问子串中至少有一个字符出现两次。

输出格式

对于每次询问，输出一行三个整数：

$$H,\quad l+SA_T[i-1]-1,\quad l+SA_T[i]-1.$$

其中 (i) 是满足 (\operatorname{height}_T[i]=H) 的最小下标。

样例输入

1
6 3
banana
1 6
1 5
2 4

样例输出

3 4 2
2 4 2
1 4 2

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1012