1833. 后缀数组

这是一道模板题。记字符串下标从 1 开始,定义串 s 的第 i 个前缀为子串 s[1..i],第 i 个后缀为子串 s[i..n]。定义 lcp(i,j) 为后缀 i,j 的最长公共前缀,lcs(i,j) 为前缀 i,j 的最长公共后缀。给定 q 组询问,每次给定 x,y,求 lcp(x,y),lcs(x,y)

输入

输入一行一个只含小写字母的字符串 s(2\le |s|\le 10^6)

接下来输入一行一个整数 q(1\le q\le10^5)

接下来输入 q 行,每行两个整数 x,y(1\le x,y\le |s|,x\neq y)

输出

输出 q 行,每行两个整数,代表 lcp(x,y)lcs(x,y)

样例

标准输入 复制文本
icpcicpc
4
1 5
2 6
1 2
2 4
标准输出 复制文本
4 1
3 2
0 0
1 1

提示

对第一个询问,lcp(1,5)=lcp(icpcicpc,icpc)=|icpc|=4lcs(1,5)=lcs(i,icpci)=|i|=1

LCP: longest common prefix, LCS: longest common suffix

22/10/01: 数据范围已修复

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 29
通过 3