#O1102. 后缀数组与 LCP

后缀数组与 LCP

题目描述

给定一个字符串 ss(下标从 11 开始),有 qq 次询问,每次给出两个位置 a,ba,b,求以 aa 开头和以 bb 开头的两个后缀的最长公共前缀长度。

输入格式

第一行一个字符串 ss。

第二行一个整数 qq。

接下来 qq 行,每行两个整数 a,ba,b。

输出格式

共 qq 行,每行一个整数,表示对应询问的 LCP 长度。

样例 #1

样例输入 #1

banana
2
2 6
4 6

样例输出 #1

1
1

数据规模与约定

数据范围 说明
$1 \le s
1≤q≤2×1041 \le q \le 2\times10^4 询问次数
  • 后缀数组 + 高度数组,LCP 即区间最小值,用 ST 表做到 O(1)O(1) 询问。
  • a=b 时答案为 ∣s∣−a+1|s|-a+1。