这是一道模板题。记字符串下标从 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|=4,lcs(1,5)=lcs(i,icpci)=|i|=1。
LCP: longest common prefix, LCS: longest common suffix
22/10/01: 数据范围已修复