#O1102. 后缀数组与 LCP
后缀数组与 LCP
题目描述
给定一个字符串 (下标从 开始),有 次询问,每次给出两个位置 ,求以 开头和以 开头的两个后缀的最长公共前缀长度。
输入格式
第一行一个字符串 。
第二行一个整数 。
接下来 行,每行两个整数 。
输出格式
共 行,每行一个整数,表示对应询问的 LCP 长度。
样例 #1
样例输入 #1
banana
2
2 6
4 6
样例输出 #1
1
1
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| $1 \le | s |
| 询问次数 |
- 后缀数组 + 高度数组,LCP 即区间最小值,用 ST 表做到 询问。
a=b时答案为 。