#P1016. 最长公共前缀

最长公共前缀

当前没有测试数据。

题目描述

给定一个字符串 SSmm 个询问,每次询问从下标 aabb 开始的两个后缀的最长公共前缀。

格式

输入格式

第一行一个字符串 SS

第二行一个整数 mm,表示询问的个数。

接下来 mm 行,每行两个整数 aabb,表示一次询问。下标从 11 开始。

输出格式

mm 行,对于每一个询问,输出其答案。

数据样例

10 3
abcabcabcd
1 4
3 9
8 9
6
1
0

数据规模与约定

  • 对于 100%100\% 的数据,1S1051\leq |S|\leq10^51m5×1051\leq m\leq 5\times10^5